{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Integer to English Words"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Hard"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #recursion #math #string"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #递归 #数学 #字符串"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: numberToWords"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #整数转换英文表示"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>将非负整数 <code>num</code> 转换为其对应的英文表示。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>num = 123\n",
    "<strong>输出：</strong>\"One Hundred Twenty Three\"\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>num = 12345\n",
    "<strong>输出：</strong>\"Twelve Thousand Three Hundred Forty Five\"\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 3：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>num = 1234567\n",
    "<strong>输出：</strong>\"One Million Two Hundred Thirty Four Thousand Five Hundred Sixty Seven\"\n",
    "</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>0 &lt;= num &lt;= 2<sup>31</sup> - 1</code></li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [integer-to-english-words](https://leetcode.cn/problems/integer-to-english-words/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [integer-to-english-words](https://leetcode.cn/problems/integer-to-english-words/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['123', '12345', '1234567']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numberToWords(self, num: int) -> str:\n",
    "        if num == 0:\n",
    "            return 'Zero'\n",
    "        dic1 = ['One', 'Two', 'Three', 'Four', 'Five', 'Six', 'Seven', 'Eight', 'Nine',\n",
    "                'Ten', 'Eleven', 'Twelve', 'Thirteen', 'Fourteen', 'Fifteen', 'Sixteen', 'Seventeen', 'Eighteen', 'Nineteen']\n",
    "        dic2 = ['Twenty', 'Thirty', 'Forty', 'Fifty', 'Sixty', 'Seventy', 'Eighty', 'Ninety']\n",
    "        segs = []\n",
    "        while num > 0:\n",
    "            segs.append(num % 1_000)\n",
    "            num //= 1_000\n",
    "        def seg_to_eng(num, pos):\n",
    "            if num == 0:\n",
    "                return ''\n",
    "            buffer = []\n",
    "            if num >= 100:\n",
    "                buffer.append(f'{dic1[num//100 - 1]} Hundred')\n",
    "                num %= 100\n",
    "            if num >= 20:\n",
    "                if num % 10 != 0:\n",
    "                    buffer.append(f'{dic2[num//10 - 2]} {dic1[num%10 - 1]}')\n",
    "                else:\n",
    "                    buffer.append(f'{dic2[num//10 - 2]}')\n",
    "            elif num > 0:\n",
    "                buffer.append(f'{dic1[num - 1]}')\n",
    "            if pos == 1:\n",
    "                buffer.append('Thousand ')\n",
    "            elif pos == 2:\n",
    "                buffer.append('Million ')\n",
    "            elif pos == 3:\n",
    "                buffer.append('Billion ')\n",
    "            return ' '.join(buffer)\n",
    "        return ''.join(reversed([seg_to_eng(n, p) for p, n in enumerate(segs)])).strip()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numberToWords(self, num: int) -> str:\n",
    "        digitMap = ['Zero', 'One', 'Two', 'Three', 'Four', 'Five', 'Six', 'Seven', 'Eight', 'Nine', 'Ten', 'Eleven', 'Twelve', 'Thirteen', 'Fourteen', 'Fifteen', 'Sixteen', 'Seventeen', 'Eighteen', 'Nineteen', 'Twenty']\n",
    "        decadeMap = {2: 'Twenty', 3: 'Thirty', 4: 'Forty', 5: 'Fifty', 6: 'Sixty', 7: 'Seventy', 8: 'Eighty', 9: 'Ninety'}\n",
    "        def toHundreds(n):\n",
    "            ws = []\n",
    "            h = n // 100\n",
    "            n %= 100\n",
    "            if h > 0:\n",
    "                ws.append(digitMap[h])\n",
    "                ws.append('Hundred')\n",
    "            if 0 < n <= 20:\n",
    "                ws.append(digitMap[n])\n",
    "            elif n > 20:\n",
    "                d = n // 10\n",
    "                ws.append(decadeMap[d])\n",
    "                if n % 10 != 0:\n",
    "                    ws.append(digitMap[n % 10])\n",
    "            return ws\n",
    "\n",
    "        if num == 0:\n",
    "            return digitMap[0]\n",
    "        mag = [1000000000, 1000000, 1000]\n",
    "        magMap = ['Billion', 'Million', 'Thousand']\n",
    "        words = []\n",
    "        for i, m in enumerate(mag):\n",
    "            h = num // m\n",
    "            num %= m\n",
    "            if h > 0:\n",
    "                words.extend(toHundreds(h))\n",
    "                words.append(magMap[i])\n",
    "        if num > 0:\n",
    "            words.extend(toHundreds(num))\n",
    "        \n",
    "        return ' '.join(words)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numberToWords(self, num):\n",
    "        d1 = [\"Zero\", \"One\", \"Two\", \"Three\", \"Four\", \"Five\", \"Six\", \"Seven\", \"Eight\", \"Nine\", \"Ten\", \"Eleven\", \"Twelve\", \"Thirteen\", \"Fourteen\", \"Fifteen\", \"Sixteen\", \"Seventeen\", \"Eighteen\", \"Nineteen\"]\n",
    "        d2 = [\"\", \"\", \"Twenty\", \"Thirty\", \"Forty\", \"Fifty\", \"Sixty\", \"Seventy\", \"Eighty\", \"Ninety\"]\n",
    "        if num<20:\n",
    "            return d1[num]\n",
    "        def part(num):\n",
    "            ans = ''\n",
    "            if num>=100:\n",
    "                ans+=d1[num//100]+' Hundred'\n",
    "                num%=100\n",
    "            if num>=20:\n",
    "                if ans:\n",
    "                    ans+=' '\n",
    "                ans+=d2[num//10]\n",
    "                num%=10\n",
    "            if num!=0:\n",
    "                if ans:\n",
    "                    ans+=' '\n",
    "                ans+=d1[num]\n",
    "            return ans\n",
    "        res=''\n",
    "        array=[0,0,0,0]\n",
    "        i=3\n",
    "        while i>=0:\n",
    "            array[i]=num%1000\n",
    "            num=num//1000\n",
    "            i-=1\n",
    "        i=0\n",
    "        while i<=3:\n",
    "            tmp=''\n",
    "            if array[i]!=0:\n",
    "                tmp=part(array[i])\n",
    "            else:\n",
    "                i+=1\n",
    "                continue\n",
    "            if i==0:\n",
    "                res+=tmp+' Billion'\n",
    "            elif i==1:\n",
    "                if res:\n",
    "                    res+=' '\n",
    "                res+=tmp+' Million'\n",
    "            elif i==2:\n",
    "                if res:\n",
    "                    res+=' '\n",
    "                res+=tmp+' Thousand'\n",
    "            else:\n",
    "                if res:\n",
    "                    res+=' '\n",
    "                res+=tmp\n",
    "            i+=1\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "singles = [\"\", \"One\", \"Two\", \"Three\", \"Four\", \"Five\", \"Six\", \"Seven\", \"Eight\", \"Nine\"]\n",
    "teens = [\"Ten\", \"Eleven\", \"Twelve\", \"Thirteen\", \"Fourteen\", \"Fifteen\", \"Sixteen\", \"Seventeen\", \"Eighteen\", \"Nineteen\"]\n",
    "tens = [\"\", \"Ten\", \"Twenty\", \"Thirty\", \"Forty\", \"Fifty\", \"Sixty\", \"Seventy\", \"Eighty\", \"Ninety\"]\n",
    "thousands = [\"\", \"Thousand\", \"Million\", \"Billion\"]\n",
    "\n",
    "class Solution:\n",
    "    def numberToWords(self, num: int) -> str:\n",
    "        if num==0:\n",
    "            return 'Zero'\n",
    "        \n",
    "        def toEng(num):\n",
    "            s=''\n",
    "            if num>=100:\n",
    "                s+=singles[num//100]+' Hundred '\n",
    "                num%=100\n",
    "            if num>=20:\n",
    "                s+=tens[num//10]+ ' '\n",
    "                num%=10\n",
    "            if 0<num<10:\n",
    "                s+=singles[num]+' '\n",
    "            elif num>=10:\n",
    "                s+=teens[num-10]+' '\n",
    "            return s\n",
    "\n",
    "        s=''\n",
    "        unit=int(1e9)\n",
    "        for i in range(3, -1, -1):\n",
    "            curNum= num//unit\n",
    "            if curNum:\n",
    "                num-=curNum*unit\n",
    "                s+= toEng(curNum)+thousands[i]+' '\n",
    "            unit //=1000\n",
    "        return s.strip()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numberToWords(self, num: int) -> str:\n",
    "        unit=['','Thousand','Million','Billion']\n",
    "        singles = [\"\", \"One\", \"Two\", \"Three\", \"Four\", \"Five\", \"Six\", \"Seven\", \"Eight\", \"Nine\"]\n",
    "        teens = [\"Ten\", \"Eleven\", \"Twelve\", \"Thirteen\", \"Fourteen\", \"Fifteen\", \"Sixteen\", \"Seventeen\", \"Eighteen\",\n",
    "                 \"Nineteen\"]\n",
    "        tens = [\"\", \"Ten\", \"Twenty\", \"Thirty\", \"Forty\", \"Fifty\", \"Sixty\", \"Seventy\", \"Eighty\", \"Ninety\"]\n",
    "        \n",
    "        if num==0:\n",
    "            return 'Zero'\n",
    "\n",
    "        resultlist=[]\n",
    "        for i in range(4):\n",
    "            number=num % 1000\n",
    "            num = (num - num % 1000) // 1000\n",
    "            if number==0:\n",
    "                continue\n",
    "            temp=[]\n",
    "            if number>=100:\n",
    "                temp.append(singles[number//100])\n",
    "                temp.append('Hundred')\n",
    "            number=number%100\n",
    "            if number<=9 and number>0:\n",
    "                temp.append(singles[number])\n",
    "            elif number>9 and number<20:\n",
    "                temp.append(teens[number-10])\n",
    "            elif number==0:\n",
    "                pass\n",
    "            else:\n",
    "                temp.append(tens[number//10])\n",
    "                if number%10>0:\n",
    "                    temp.append(singles[number%10])\n",
    "            temp.append(unit[i])\n",
    "            resultlist=temp+resultlist\n",
    "\n",
    "        return  ' '.join(resultlist).strip()\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "basics = ['','One','Two','Three','Four','Five','Six','Seven','Eight','Nine','Ten','Eleven','Twelve','Thirteen','Fourteen','Fifteen','Sixteen','Seventeen','Eighteen','Nineteen']\n",
    "tens = ['','','Twenty','Thirty','Forty','Fifty','Sixty','Seventy','Eighty','Ninety']\n",
    "class Solution:\n",
    "    def numberToWords(self, num: int) -> str:\n",
    "        def num2Eng(s):\n",
    "            if num==0:\n",
    "                return 'Zero'\n",
    "            if s<20:\n",
    "                return basics[s]\n",
    "            elif s<100: #十\n",
    "                a,b=s//10,s%10\n",
    "                if b!=0:\n",
    "                    return tens[a]+' '+basics[b]\n",
    "                else:\n",
    "                    return tens[a]\n",
    "            elif s<1000: #百\n",
    "                a,b=s//100,s%100\n",
    "                if b!=0:\n",
    "                    return basics[a]+' Hundred '+num2Eng(b)\n",
    "                else:\n",
    "                    return basics[a]+' Hundred'\n",
    "            elif s<1000000: #用Thousand计量\n",
    "                a,b=s//1000,s%1000\n",
    "                if b!=0:\n",
    "                    return num2Eng(a)+' Thousand '+num2Eng(b)\n",
    "                else:\n",
    "                    return num2Eng(a)+' Thousand'\n",
    "            elif s<1E9: #用Million计量\n",
    "                a,b=s//1000000,s%1000000\n",
    "                if b!=0:\n",
    "                    return num2Eng(a)+' Million '+num2Eng(b)\n",
    "                else:\n",
    "                    return num2Eng(a)+' Million'\n",
    "            else: #用Billion计量\n",
    "                a,b=s//1000000000,s%1000000000\n",
    "                if b!=0:\n",
    "                    return num2Eng(a)+' Billion '+num2Eng(b)\n",
    "                else:\n",
    "                    return num2Eng(a)+' Billion'\n",
    "        return num2Eng(num)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numberToWords(self, num: int) -> str:\n",
    "        oneDigitWords={\n",
    "            1:'One',\n",
    "            2:'Two',\n",
    "            3:'Three',\n",
    "            4:'Four',\n",
    "            5:'Five',\n",
    "            6:'Six',\n",
    "            7:'Seven',\n",
    "            8:'Eight',\n",
    "            9:'Nine'\n",
    "        }\n",
    "        twoDigitWords={\n",
    "            20:'Twenty',\n",
    "            30:'Thirty',\n",
    "            40:'Forty',\n",
    "            50:'Fifty',\n",
    "            60:'Sixty',\n",
    "            70:'Seventy',\n",
    "            80:'Eighty',\n",
    "            90:'Ninety'\n",
    "        }\n",
    "        tenWords={\n",
    "            10:'Ten',\n",
    "            11:'Eleven',\n",
    "            12:'Twelve',\n",
    "            13:'Thirteen',\n",
    "            14:'Fourteen',\n",
    "            15:'Fifteen',\n",
    "            16:'Sixteen',\n",
    "            17:'Seventeen',\n",
    "            18:'Eighteen',\n",
    "            19:'Nineteen'\n",
    "        }\n",
    "        def seg_to_str(seg):\n",
    "            if seg==0:\n",
    "                return ''\n",
    "            result=''\n",
    "            if seg>=100:\n",
    "                result+=oneDigitWords[seg//100]+' Hundred '\n",
    "            seg=seg%100\n",
    "            if seg==0:\n",
    "                return result.rstrip()\n",
    "            if seg>=20:\n",
    "                a=seg%10\n",
    "                if a==0:\n",
    "                    result+=twoDigitWords[seg-a]\n",
    "                else:\n",
    "                    result+=twoDigitWords[seg-a]+' '+oneDigitWords[a]\n",
    "            elif seg>=10:\n",
    "                result+=tenWords[seg]\n",
    "            else:\n",
    "                result+=oneDigitWords[seg]\n",
    "            return result.rstrip()\n",
    "\n",
    "        if num==0:\n",
    "            return 'Zero'\n",
    "        i=1000\n",
    "        num_segs=[]\n",
    "        while num>0:\n",
    "            num_segs.insert(0,seg_to_str(num%1000))\n",
    "            num//=1000\n",
    "\n",
    "        n=len(num_segs)\n",
    "        result=num_segs[-1]\n",
    "        segWords=['','Thousand','Million','Billion']\n",
    "        for i in range(1,n):\n",
    "            if num_segs[-1-i]!='':\n",
    "                result=num_segs[-1-i]+' '+segWords[i]+' '+result\n",
    "        return result.rstrip()\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numberToWords(self, num: int) -> str:\n",
    "        digitMap = ['Zero', 'One', 'Two', 'Three', 'Four', 'Five', 'Six', 'Seven', 'Eight', 'Nine', 'Ten', 'Eleven', 'Twelve', 'Thirteen', 'Fourteen', 'Fifteen', 'Sixteen', 'Seventeen', 'Eighteen', 'Nineteen', 'Twenty']\n",
    "        decadeMap = {2: 'Twenty', 3: 'Thirty', 4: 'Forty', 5: 'Fifty', 6: 'Sixty', 7: 'Seventy', 8: 'Eighty', 9: 'Ninety'}\n",
    "        def toHundreds(n):\n",
    "            ws = []\n",
    "            h = n // 100\n",
    "            n %= 100\n",
    "            if h > 0:\n",
    "                ws.append(digitMap[h])\n",
    "                ws.append('Hundred')\n",
    "            if 0 < n <= 20:\n",
    "                ws.append(digitMap[n])\n",
    "            elif n > 20:\n",
    "                d = n // 10\n",
    "                ws.append(decadeMap[d])\n",
    "                if n % 10 != 0:\n",
    "                    ws.append(digitMap[n % 10])\n",
    "            return ws\n",
    "        if num == 0:\n",
    "            return digitMap[0]\n",
    "        mag = [1000000000, 1000000, 1000]\n",
    "        magMap = ['Billion', 'Million', 'Thousand']\n",
    "        words = []\n",
    "        for i, m in enumerate(mag):\n",
    "            h = num // m\n",
    "            num %= m\n",
    "            if h > 0:\n",
    "                words.extend(toHundreds(h))\n",
    "                words.append(magMap[i])\n",
    "        if num > 0:\n",
    "            words.extend(toHundreds(num))\n",
    "        return ' '.join(words)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numberToWords(self, num: int) -> str:\n",
    "        if num == 0:\n",
    "            return 'Zero'\n",
    "        singles = [\"\", \"One\", \"Two\", \"Three\", \"Four\", \"Five\", \"Six\", \"Seven\", \"Eight\", \"Nine\"]\n",
    "        teens = [\"Ten\", \"Eleven\", \"Twelve\", \"Thirteen\", \"Fourteen\", \"Fifteen\", \"Sixteen\", \"Seventeen\", \"Eighteen\", \"Nineteen\"]\n",
    "        tens = [\"\", \"Ten\", \"Twenty\", \"Thirty\", \"Forty\", \"Fifty\", \"Sixty\", \"Seventy\", \"Eighty\", \"Ninety\"]\n",
    "        thousands = [\"\", \"Thousand\", \"Million\", \"Billion\"]\n",
    "        ans = []\n",
    "        n1000 = 0\n",
    "        while num > 0:\n",
    "            n100 = (num % 1000) // 100\n",
    "            n10 = (num % 100) // 10\n",
    "            n1 = num % 10\n",
    "            num //= 1000\n",
    "            t = []\n",
    "            if n100 > 0:\n",
    "                t += [singles[n100], 'Hundred']\n",
    "            if n10 > 1:\n",
    "                t += [tens[n10]]\n",
    "            if n10 == 1:\n",
    "                if n1 == 0:\n",
    "                    t += [tens[n10]]\n",
    "                else:\n",
    "                    t += [teens[n1]]\n",
    "            elif n1 > 0:\n",
    "                t += [singles[n1]]\n",
    "            if n1000 > 0 and t:\n",
    "                t += [thousands[n1000]]\n",
    "            n1000 += 1\n",
    "            ans = t + ans\n",
    "        return ' '.join(ans)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numberToWords(self, num: int) -> str:\n",
    "        if num == 0:\n",
    "            return 'Zero'\n",
    "        singles = [\"\", \"One\", \"Two\", \"Three\", \"Four\", \"Five\", \"Six\", \"Seven\", \"Eight\", \"Nine\"]\n",
    "        teens = [\"Ten\", \"Eleven\", \"Twelve\", \"Thirteen\", \"Fourteen\", \"Fifteen\", \"Sixteen\", \"Seventeen\", \"Eighteen\", \"Nineteen\"]\n",
    "        tens = [\"\", \"Ten\", \"Twenty\", \"Thirty\", \"Forty\", \"Fifty\", \"Sixty\", \"Seventy\", \"Eighty\", \"Ninety\"]\n",
    "        thousands = [\"\", \"Thousand\", \"Million\", \"Billion\"]\n",
    "        digits = [0, 0, 0, 0] + [int(c) for c in str(num)]\n",
    "        ans = []\n",
    "        n1000 = 0\n",
    "        while num > 0:\n",
    "            n100 = digits[-n1000 * 3 - 3]\n",
    "            n10 = digits[-n1000 * 3 - 2]\n",
    "            n1 = digits[-n1000 * 3 - 1]\n",
    "            num //= 1000\n",
    "            t = []\n",
    "            if n100 > 0:\n",
    "                t += [singles[n100], 'Hundred']\n",
    "            if n10 > 1:\n",
    "                t += [tens[n10]]\n",
    "            if n10 == 1:\n",
    "                if n1 == 0:\n",
    "                    t += [tens[n10]]\n",
    "                else:\n",
    "                    t += [teens[n1]]\n",
    "            elif n1 > 0:\n",
    "                t += [singles[n1]]\n",
    "            if n1000 > 0 and t:\n",
    "                t += [thousands[n1000]]\n",
    "            n1000 += 1\n",
    "            ans = t + ans\n",
    "        return ' '.join(ans)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numberToWordsWithThreeBits(slef, num: int)->str:\n",
    "        numbers = [\"\", \"One\", \"Two\", \"Three\", \"Four\", \"Five\", \"Six\", \"Seven\", \"Eight\", \"Nine\", \"Ten\",\n",
    "        \"Eleven\", \"Twelve\", \"Thirteen\", \"Fourteen\", \"Fifteen\", \"Sixteen\", \"Seventeen\", \"Eighteen\", \"Nineteen\",\n",
    "        \"Twenty\"]\n",
    "        ten_bits = [\"\", \"Ten\", \"Twenty\", \"Thirty\", \"Forty\", \"Fifty\", \"Sixty\", \"Seventy\", \"Eighty\", \"Ninety\"]\n",
    "        res = \"\"\n",
    "        if num == 0:\n",
    "            return \"\"\n",
    "        if num >= 100:\n",
    "            res += numbers[num//100] + \" Hundred\"\n",
    "            num = num % 100\n",
    "        if num == 0:\n",
    "            return res\n",
    "        elif num <= 20:\n",
    "            res += \" \" + numbers[num]\n",
    "        elif num % 10 == 0:\n",
    "            res += \" \" + ten_bits[num//10]\n",
    "        else:\n",
    "            ten_bit = num // 10\n",
    "            one_bit = num % 10\n",
    "            res += \" \" + ten_bits[ten_bit] + \" \" + numbers[one_bit]\n",
    "        return res.strip(\" \")\n",
    "        \n",
    "    def numberToWords(self, num: int) -> str:\n",
    "        if num == 0:\n",
    "            return \"Zero\"\n",
    "        three_bits = [\"\",\"Thousand\", \"Million\", \"Billion\"]\n",
    "        result = \"\"\n",
    "        cnt = 0\n",
    "        while not num == 0:\n",
    "            temp = num % 1000\n",
    "            num = num // 1000\n",
    "            temp_str = self.numberToWordsWithThreeBits(temp)\n",
    "            if not temp_str == \"\":\n",
    "                result =  temp_str + ' ' + three_bits[cnt] + ' ' + result\n",
    "            cnt += 1\n",
    "        return result.strip(\" \")"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "singles=[\"\",\"One\",\"Two\",\"Three\",\"Four\",\"Five\",\"Six\",\"Seven\",\"Eight\",\"Nine\"]\n",
    "teens=[\"Ten\",\"Eleven\",\"Twelve\",\"Thirteen\",\"Fourteen\",\"Fifteen\",\"Sixteen\",\"Seventeen\",\"Eighteen\",\"Nineteen\"]\n",
    "tens=[\"\",\"Ten\",\"Twenty\",\"Thirty\",\"Forty\",\"Fifty\",\"Sixty\",\"Seventy\",\"Eighty\",\"Ninety\"]\n",
    "thousands=[\"\",\"Thousand\",\"Million\",\"Billion\"]\n",
    "class Solution:\n",
    "    def numberToWords(self, num: int) -> str:\n",
    "        if num == 0:\n",
    "            return \"Zero\"\n",
    "        def toEnglish(num:int) -> str:\n",
    "            s = \"\"\n",
    "            if num >= 100:\n",
    "                s += singles[num//100]+\" Hundred \"\n",
    "                num %= 100\n",
    "            if num >= 20:\n",
    "                s += tens[num//10] + \" \"\n",
    "                num %= 10\n",
    "            if 0 < num < 10:\n",
    "                s += singles[num] + \" \"\n",
    "            if num >= 10:\n",
    "                s += teens[num - 10] + \" \"\n",
    "            return s\n",
    "\n",
    "        s = \"\"\n",
    "        unit = int(1e9)\n",
    "        for i in range(3,-1,-1):\n",
    "            curNum = num // unit\n",
    "            if curNum:\n",
    "                num -=curNum * unit\n",
    "                s += toEnglish(curNum) + thousands[i] +\" \"\n",
    "            unit //= 1000\n",
    "        return s.strip()\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "dic = {1: \"One\", 2: \"Two\", 3: \"Three\",\n",
    "       4: \"Four\", 5: \"Five\", 6: \"Six\",\n",
    "       7: \"Seven\", 8: \"Eight\", 9: \"Nine\"}\n",
    "dic11 = {10: \"Ten\", \n",
    "         11: \"Eleven\", 12: \"Twelve\", 13: \"Thirteen\",\n",
    "         14: \"Fourteen\", 15: \"Fifteen\", 16: \"Sixteen\",\n",
    "         17: \"Seventeen\", 18: \"Eighteen\", 19: \"Nineteen\"}\n",
    "dic20 = {2: \"Twenty\", 3: \"Thirty\", \n",
    "         4: \"Forty\", 5: \"Fifty\", 6: \"Sixty\",\n",
    "         7: \"Seventy\", 8: \"Eighty\", 9: \"Ninety\"}\n",
    "\n",
    "\n",
    "class Solution:\n",
    "\n",
    "    def numberToWords(self, num: int) -> str:\n",
    "        if num == 0:\n",
    "            return \"Zero\"\n",
    "\n",
    "        ans = []\n",
    "        if num >= 1000000000:\n",
    "            t1 = num // 1000000000\n",
    "            ans += self.trans1000(t1) + [\"Billion\"]\n",
    "            num -= t1 * 1000000000\n",
    "        if num >= 1000000:\n",
    "            t2 = num // 1000000\n",
    "            ans += self.trans1000(t2) + [\"Million\"]\n",
    "            num -= t2 * 1000000\n",
    "        if num >= 1000:\n",
    "            t3 = num // 1000\n",
    "            ans += self.trans1000(t3) + [\"Thousand\"]\n",
    "            num -= t3 * 1000\n",
    "        ans += self.trans1000(num)\n",
    "        return \" \".join(ans)\n",
    "\n",
    "    def trans1000(self, num: int) -> List[str]:\n",
    "        hundred = num // 100\n",
    "        ten = (num % 100) // 10\n",
    "        one = num % 10\n",
    "        ans = []\n",
    "        if hundred > 0: ans += [dic[hundred], \"Hundred\"]\n",
    "        if ten == 1: ans.append(dic11[10 + one])\n",
    "        if ten >= 2: ans.append(dic20[ten])\n",
    "        if one > 0 and ten != 1: ans.append(dic[one])\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numberToWords(self, num: int) -> str:\n",
    "\n",
    "        if num == 0:\n",
    "            return 'Zero'\n",
    "\n",
    "        def hund(self, num):\n",
    "            num = num % 1000\n",
    "            if not num:\n",
    "                return ''\n",
    "            res = ''\n",
    "            h_list = ['One','Two','Three','Four','Five','Six','Seven','Eight','Nine']\n",
    "            if num > 99:\n",
    "                h = num // 100\n",
    "                res += h_list[h-1] + ' Hundred'\n",
    "                if (num % 100) != 0:\n",
    "                    res += ' '\n",
    "\n",
    "            t = (num % 100) // 10\n",
    "            y = num % 10\n",
    "            t_list = ['Twenty','Thirty','Forty','Fifty','Sixty','Seventy','Eighty','Ninety']\n",
    "            if t >=2:\n",
    "                res += t_list[t-2]\n",
    "                if y != 0:\n",
    "                    res += ' '+h_list[y-1]\n",
    "            elif t == 1:\n",
    "                teen_list = ['Ten','Eleven','Twelve','Thirteen','Fourteen','Fifteen','Sixteen',\n",
    "                             'Seventeen','Eighteen','Nineteen']\n",
    "                res += teen_list[y]\n",
    "            else:\n",
    "                if y != 0:\n",
    "                    res += h_list[y-1]\n",
    "            return res\n",
    "\n",
    "        Bil = num // (10**9)\n",
    "        Mil = (num % (10**9)) // (10**6)\n",
    "        Thou = (num % (10**6)) // (10**3)\n",
    "        One = num % (10**3)\n",
    "        res = ''\n",
    "        if Bil:\n",
    "            res += hund(self, Bil) + ' Billion'\n",
    "        if Mil:\n",
    "            if res != '':\n",
    "                res += ' '\n",
    "            res += hund(self, Mil) + ' Million'\n",
    "        if Thou:\n",
    "            if res != '':\n",
    "                res += ' '\n",
    "            res += hund(self, Thou) + ' Thousand'\n",
    "        if One:\n",
    "            if res != '':\n",
    "                res += ' '\n",
    "            res += hund(self, One)\n",
    "\n",
    "        return res "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "singles = ['Zero', 'One', 'Two', 'Three', 'Four', 'Five', 'Six', 'Seven', 'Eight', 'Nine', 'Ten', 'Eleven', 'Twelve', 'Thirteen', 'Fourteen', 'Fifteen', 'Sixteen', 'Seventeen', 'Eighteen', 'Nineteen']\n",
    "tens = ['', '', 'Twenty', 'Thirty', 'Forty', 'Fifty', 'Sixty', 'Seventy', 'Eighty', 'Ninety']\n",
    "levels = ['', 'Thousand', 'Million', 'Billion']\n",
    "\n",
    "class Solution:\n",
    "    def numberToWords(self, num: int) -> str:\n",
    "        if num < 20:\n",
    "            return singles[num]\n",
    "\n",
    "        def converte(n):\n",
    "            if n >= 100:\n",
    "                q, n = divmod(n, 100)\n",
    "                res.append(f'{singles[q]} Hundred')\n",
    "            if n >= 20:\n",
    "                q, n = divmod(n, 10)\n",
    "                res.append(tens[q])\n",
    "            if n > 0:\n",
    "                res.append(singles[n])\n",
    "\n",
    "        res = []\n",
    "        if num >= 1000000000:\n",
    "            n, num = divmod(num, 1000000000)\n",
    "            converte(n)\n",
    "            res.append(levels[-1])\n",
    "        if num >= 1000000:\n",
    "            n, num = divmod(num, 1000000)\n",
    "            converte(n)\n",
    "            res.append(levels[-2])\n",
    "        if num >= 1000:\n",
    "            n, num = divmod(num, 1000)\n",
    "            converte(n)\n",
    "            res.append(levels[-3])\n",
    "        if num > 0:\n",
    "            converte(num)\n",
    "        return ' '.join(res)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numberToWords(self, num: int) -> str:\n",
    "        digitMap = ['Zero', 'One', 'Two', 'Three', 'Four', 'Five', 'Six', 'Seven', 'Eight', 'Nine', 'Ten', 'Eleven', 'Twelve', 'Thirteen', 'Fourteen', 'Fifteen', 'Sixteen', 'Seventeen', 'Eighteen', 'Nineteen', 'Twenty']\n",
    "        decadeMap = {2: 'Twenty', 3: 'Thirty', 4: 'Forty', 5: 'Fifty', 6: 'Sixty', 7: 'Seventy', 8: 'Eighty', 9: 'Ninety'}\n",
    "        def toHundreds(n):\n",
    "            ws = []\n",
    "            h = n // 100\n",
    "            n %= 100\n",
    "            if h > 0:\n",
    "                ws.append(digitMap[h])\n",
    "                ws.append('Hundred')\n",
    "            if 0 < n <= 20:\n",
    "                ws.append(digitMap[n])\n",
    "            elif n > 20:\n",
    "                d = n // 10\n",
    "                ws.append(decadeMap[d])\n",
    "                if n % 10 != 0:\n",
    "                    ws.append(digitMap[n % 10])\n",
    "            return ws\n",
    "\n",
    "        if num == 0:\n",
    "            return digitMap[0]\n",
    "        mag = [1000000000, 1000000, 1000]\n",
    "        magMap = ['Billion', 'Million', 'Thousand']\n",
    "        words = []\n",
    "        for i, m in enumerate(mag):\n",
    "            h = num // m\n",
    "            num %= m\n",
    "            if h > 0:\n",
    "                words.extend(toHundreds(h))\n",
    "                words.append(magMap[i])\n",
    "        if num > 0:\n",
    "            words.extend(toHundreds(num))\n",
    "        \n",
    "        return ' '.join(words)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numberToWords(self, num: int) -> str:\n",
    "        if num==0:\n",
    "            return 'Zero'\n",
    "        from0to19 = [\"\", \"One\", \"Two\", \"Three\", \"Four\", \"Five\", \"Six\", \"Seven\", \"Eight\", \"Nine\", \"Ten\", \n",
    "        \"Eleven\", \"Twelve\", \"Thirteen\", \"Fourteen\", \"Fifteen\", \"Sixteen\", \"Seventeen\", \"Eighteen\", \"Nineteen\"]\n",
    "\n",
    "        from20to90 = [\"\", \"\", \"Twenty\", \"Thirty\", \"Forty\", \"Fifty\", \"Sixty\", \"Seventy\", \"Eighty\", \"Ninety\"]\n",
    "\n",
    "        \n",
    "\n",
    "        def trans(num)->str:\n",
    "            ret = []\n",
    "            if num==0:\n",
    "                return ret\n",
    "            a = num//100\n",
    "            num = num%100\n",
    "            if a>0:\n",
    "                ret.append(from0to19[a])\n",
    "                ret.append('Hundred')\n",
    "            if num <20:\n",
    "                ret.append(from0to19[num])\n",
    "            elif num >=20:\n",
    "                ret.append(from20to90[num//10])\n",
    "                if num%10>0:\n",
    "                    ret.append(from0to19[num%10])\n",
    "            return ret\n",
    "\n",
    "\n",
    "        res = []\n",
    "        b = num//1000000000\n",
    "\n",
    "        num = num%1000000000\n",
    "        if b>0:\n",
    "            res+=trans(b)\n",
    "            res.append('Billion')\n",
    "        \n",
    "        b = num//1000000\n",
    "        num = num%1000000\n",
    "        if b>0:\n",
    "            res+=trans(b)\n",
    "            res.append('Million')\n",
    "\n",
    "        b = num//1000\n",
    "        num = num%1000\n",
    "        if b>0:\n",
    "            res+=trans(b)\n",
    "            res.append('Thousand')\n",
    "        \n",
    "        if num>0:\n",
    "            res+=trans(num)\n",
    "\n",
    "        return \" \".join([x for x in res if x!='' ])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    DICT =[\n",
    "        \"\",\"One\",\"Two\",\"Three\",\"Four\",\"Five\",\"Six\",\"Seven\",\"Eight\",\"Nine\",\n",
    "        \"Ten\",\"Eleven\",\"Twelve\",\"Thirteen\",\"Fourteen\",\"Fifteen\",\"Sixteen\",\"Seventeen\",\"Eighteen\", \"Nineteen\"]\n",
    "    \n",
    "    TY = [\"Twenty\",\"Thirty\",\"Forty\",\"Fifty\",\"Sixty\",\"Seventy\",\"Eighty\",\"Ninety\"]\n",
    "    \n",
    "\n",
    "    def numberToWords(self, num: int) -> str:\n",
    "        if num == 0:\n",
    "            return \"Zero\"\n",
    "        \n",
    "        b = int(num / 1_000_000_000)\n",
    "        m = int(num % 1_000_000_000 / 1_000_000)\n",
    "        t = int(num % 1_000_000 / 1_000)\n",
    "        n = int(num % 1_000 )\n",
    "\n",
    "        # print(b,m,t,n)\n",
    "        \n",
    "        rst = []\n",
    "        if b != 0:\n",
    "            rst.append(self.getNumWords(b) + \" Billion\")\n",
    "        if m != 0:\n",
    "            rst.append(self.getNumWords(m) + \" Million\")\n",
    "        if t != 0:\n",
    "            rst.append(self.getNumWords(t) + \" Thousand\")\n",
    "        if n != 0:\n",
    "            rst.append(self.getNumWords(n))\n",
    "        return \" \".join(rst)\n",
    "\n",
    "    \n",
    "    def getNumWords(self, num: int) :\n",
    "        rst_l = []\n",
    "        h = int(num / 100)\n",
    "        if h > 0:\n",
    "            rst_l.append(self.DICT[h] + \" Hundred\")\n",
    "        \n",
    "        t = num % 100 \n",
    "        if 0 < t < 20:\n",
    "            rst_l.append(self.DICT[t])\n",
    "        elif t >= 20:\n",
    "            tf = int(t/10)\n",
    "            # print(num, t, tf)\n",
    "            rst_l.append(self.TY[tf-2])\n",
    "            ts = t%10\n",
    "            if ts > 0:\n",
    "                rst_l.append(self.DICT[ts])\n",
    "        return \" \".join(rst_l)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numberToWords(self, num: int) -> str:\n",
    "        if num == 0: return \"Zero\"\n",
    "\n",
    "        trans = {\n",
    "            1: 'One', \n",
    "            2: 'Two', \n",
    "            3: 'Three', \n",
    "            4: 'Four', \n",
    "            5: 'Five', \n",
    "            6: 'Six', \n",
    "            7: 'Seven', \n",
    "            8: 'Eight', \n",
    "            9: 'Nine', \n",
    "            10: 'Ten', \n",
    "            11: 'Eleven', \n",
    "            12: 'Twelve', \n",
    "            13: 'Thirteen', \n",
    "            14: 'Fourteen', \n",
    "            15: 'Fifteen', \n",
    "            16: 'Sixteen', \n",
    "            17: 'Seventeen', \n",
    "            18: 'Eighteen', \n",
    "            19: 'Nineteen', \n",
    "            20: 'Twenty', \n",
    "            30: 'Thirty', \n",
    "            40: 'Forty', \n",
    "            50: 'Fifty', \n",
    "            60: 'Sixty', \n",
    "            70: 'Seventy', \n",
    "            80: 'Eighty', \n",
    "            90: 'Ninety'\n",
    "        }\n",
    "\n",
    "        def get_3_digit_name(three_digit): \n",
    "            sub_res = [] \n",
    "            if three_digit >= 100: \n",
    "                sub_res.append(trans[three_digit // 100]) \n",
    "                sub_res.append('Hundred') \n",
    "                three_digit %= 100 \n",
    "            if 0 < three_digit <= 19: \n",
    "                sub_res.append(trans[three_digit]) \n",
    "            elif three_digit >= 20: \n",
    "                sub_res.append(trans[three_digit // 10 * 10])\n",
    "                if three_digit % 10 > 0: \n",
    "                    sub_res.append(trans[three_digit % 10]) \n",
    "\n",
    "            return sub_res \n",
    "                \n",
    "\n",
    "        res = []\n",
    "        if num >= 1000000000: \n",
    "            res.append(trans[num // 1000000000])\n",
    "            res.append('Billion') \n",
    "            num = num % 1000000000\n",
    "\n",
    "        if num >= 1000000: \n",
    "            res = res + get_3_digit_name(num // 1000000)\n",
    "            num = num % 1000000\n",
    "            res.append('Million')\n",
    "\n",
    "        if num >= 1000:\n",
    "            res = res + get_3_digit_name(num // 1000)\n",
    "            num = num % 1000\n",
    "            res.append('Thousand')\n",
    "\n",
    "        if num > 0: \n",
    "            res = res + get_3_digit_name(num)\n",
    "        \n",
    "        return ' '.join(res)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def __init__(self):\n",
    "        self.nt = [\"Zero\", \"One\", \"Two\", \"Three\", \"Four\", \"Five\", \"Six\", \"Seven\", \"Eight\", \"Nine\", \"Ten\", \"Eleven\", \"Twelve\",\n",
    "        \"Thirteen\", \"Fourteen\", \"Fifteen\", \"Sixteen\", \"Seventeen\", \"Eighteen\", \"Nineteen\"]\n",
    "        self.tens = [\"\", \"\", \"Twenty\", \"Thirty\", \"Forty\", \"Fifty\", \"Sixty\", \"Seventy\", \"Eighty\", \"Ninety\"]\n",
    "        self.t = [\"Thousand\", \"Million\", \"Billion\"]\n",
    "\n",
    "    def numberToWords(self, num: int) -> str:\n",
    "        def helper(num) -> list[str]:\n",
    "            if num < 20:\n",
    "                return [self.nt[num]]\n",
    "            elif num < 100:\n",
    "                res = [self.tens[num//10]]\n",
    "                if num % 10:\n",
    "                    res += helper(num % 10)\n",
    "                return res\n",
    "            elif num < 1000:\n",
    "                res = [self.nt[num//100], \"Hundred\"]\n",
    "                if num % 100:\n",
    "                    res += helper(num%100)\n",
    "                return res\n",
    "            for p, w in enumerate(self.t, 1):\n",
    "                if num < 1000 ** (p + 1):\n",
    "                    return helper(num // 1000 ** p) + [w] + helper(num % 1000 ** p) if num % 1000 ** p else helper(num // 1000 ** p) + [w]\n",
    "        return \" \".join(helper(num))\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numberToWords(self, num: int) -> str:\n",
    "\n",
    "\n",
    "        # 三个一组 每组单位\n",
    "        if num == 0: return \"Zero\"\n",
    "        singles = [\"\", \"One\", \"Two\", \"Three\", \"Four\", \"Five\", \"Six\", \"Seven\", \"Eight\", \"Nine\"]\n",
    "        teens = [\"Ten\", \"Eleven\", \"Twelve\", \"Thirteen\", \"Fourteen\", \"Fifteen\", \"Sixteen\", \"Seventeen\", \"Eighteen\", \"Nineteen\"]\n",
    "        tens = [\"\", \"Ten\", \"Twenty\", \"Thirty\", \"Forty\", \"Fifty\", \"Sixty\", \"Seventy\", \"Eighty\", \"Ninety\"]\n",
    "        thousands = [\"\", \"Thousand\", \"Million\", \"Billion\"]\n",
    "        # 递归\n",
    "        def num2str(num_):\n",
    "            s = \"\"\n",
    "            if num_ == 0:\n",
    "                return s\n",
    "            if 0< num_ < 10:\n",
    "                return  s + singles[num_] + \" \"\n",
    "            if 10<= num_ < 20:\n",
    "                return s + teens[num_%10] + \" \"\n",
    "            if 20<= num_ < 100:\n",
    "                return s + tens[num_//10] + \" \" + num2str(num_ % 10)\n",
    "            if 100<= num_:\n",
    "                return s + singles[num_//100] + \" Hundred \" + num2str(num_ % 100) \n",
    "        results = \"\"\n",
    "        unit = int(1e9)\n",
    "        # n = len(groups)\n",
    "        for i in range(3, -1, -1):\n",
    "            cur = num // unit\n",
    "            if cur:\n",
    "                results += num2str(cur) + thousands[i] + \" \"\n",
    "                num -= cur * unit\n",
    "            unit //= 1000\n",
    "\n",
    "        return results.strip()\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "singles = [\"\", \"One\", \"Two\", \"Three\", \"Four\", \"Five\", \"Six\", \"Seven\", \"Eight\", \"Nine\"]\n",
    "teens = [\"Ten\", \"Eleven\", \"Twelve\", \"Thirteen\", \"Fourteen\", \"Fifteen\", \"Sixteen\", \"Seventeen\", \"Eighteen\", \"Nineteen\"]\n",
    "tens = [\"\", \"Ten\", \"Twenty\", \"Thirty\", \"Forty\", \"Fifty\", \"Sixty\", \"Seventy\", \"Eighty\", \"Ninety\"]\n",
    "thousands = [\"\", \"Thousand\", \"Million\", \"Billion\"]\n",
    "\n",
    "class Solution:\n",
    "    def numberToWords(self, num: int) -> str:\n",
    "        if num == 0:\n",
    "            return \"Zero\"\n",
    "\n",
    "        def recursion(num: int) -> str:\n",
    "            s = \"\"\n",
    "            if num == 0:\n",
    "                return s\n",
    "            elif num < 10:\n",
    "                s += singles[num] + \" \"\n",
    "            elif num < 20:\n",
    "                s += teens[num - 10] + \" \"\n",
    "            elif num < 100:\n",
    "                s += tens[num // 10] + \" \" + recursion(num % 10)\n",
    "            else:\n",
    "                s += singles[num // 100] + \" Hundred \" + recursion(num % 100)\n",
    "            return s\n",
    "\n",
    "        s = \"\"\n",
    "        unit = int(1e9)\n",
    "        for i in range(3, -1, -1):\n",
    "            curNum = num // unit\n",
    "            if curNum:\n",
    "                num -= curNum * unit\n",
    "                s += recursion(curNum) + thousands[i] + \" \"\n",
    "            unit //= 1000\n",
    "        return s.strip()\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numberToWords(self, num: int) -> str:\n",
    "        digitMap = ['Zero', 'One', 'Two', 'Three', 'Four', 'Five', 'Six', 'Seven', 'Eight', 'Nine', 'Ten', 'Eleven', 'Twelve', 'Thirteen', 'Fourteen', 'Fifteen', 'Sixteen', 'Seventeen', 'Eighteen', 'Nineteen', 'Twenty']\n",
    "        decadeMap = {2: 'Twenty', 3: 'Thirty', 4: 'Forty', 5: 'Fifty', 6: 'Sixty', 7: 'Seventy', 8: 'Eighty', 9: 'Ninety'}\n",
    "        def toHundreds(n):\n",
    "            ws = []\n",
    "            h = n // 100\n",
    "            n %= 100\n",
    "            if h > 0:\n",
    "                ws.append(digitMap[h])\n",
    "                ws.append('Hundred')\n",
    "            if 0 < n <= 20:\n",
    "                ws.append(digitMap[n])\n",
    "            elif n > 20:\n",
    "                d = n // 10\n",
    "                ws.append(decadeMap[d])\n",
    "                if n % 10 != 0:\n",
    "                    ws.append(digitMap[n % 10])\n",
    "            return ws\n",
    "\n",
    "        if num == 0:\n",
    "            return digitMap[0]\n",
    "        mag = [1000000000, 1000000, 1000]\n",
    "        magMap = ['Billion', 'Million', 'Thousand']\n",
    "        words = []\n",
    "        for i, m in enumerate(mag):\n",
    "            h = num // m\n",
    "            num %= m\n",
    "            if h > 0:\n",
    "                words.extend(toHundreds(h))\n",
    "                words.append(magMap[i])\n",
    "        if num > 0:\n",
    "            words.extend(toHundreds(num))\n",
    "        \n",
    "        return ' '.join(words)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numberToWords(self, num: int) -> str:\n",
    "        mapping = {\n",
    "          1000000000: 'Billion',\n",
    "          1000000: 'Million',\n",
    "          1000: 'Thousand',\n",
    "          100: 'Hundred',\n",
    "          90: 'Ninety',\n",
    "          80: 'Eighty',\n",
    "          70: 'Seventy',\n",
    "          60: 'Sixty',\n",
    "          50: 'Fifty',\n",
    "          40: 'Forty',\n",
    "          30: 'Thirty',\n",
    "          20: 'Twenty',\n",
    "          19: 'Nineteen',\n",
    "          18: 'Eighteen',\n",
    "          17: 'Seventeen',\n",
    "          16: 'Sixteen',\n",
    "          15: 'Fifteen',\n",
    "          14: 'Fourteen',\n",
    "          13: 'Thirteen',\n",
    "          12: 'Twelve',\n",
    "          11: 'Eleven',\n",
    "          10: 'Ten',\n",
    "          9: 'Nine',\n",
    "          8: 'Eight',\n",
    "          7: 'Seven',\n",
    "          6: 'Six',\n",
    "          5: 'Five',\n",
    "          4: 'Four',\n",
    "          3: 'Three',\n",
    "          2: 'Two',\n",
    "          1: 'One'\n",
    "        }\n",
    "        if num==0: #给的是0，直接不干了\n",
    "            return \"Zero\"\n",
    "        result=\"\"\n",
    "        \n",
    "        for value, name in mapping.items():\n",
    "            count=0 #用于存储当前 value 可以完全被 num 整除的次数。\n",
    "            if num>=value:\n",
    "               count=num//value #几倍整除（进 1/2/3之类的）\n",
    "               num = num% value #余数（num应该被更新为剩下的\n",
    "\n",
    "               #开始往res里面加东西，但是分情况\n",
    "               if  value>=100: #大于一百就需要更详细的描述，需要 x hundred里面的x，而不像是100以下都很具体\n",
    "                   result= result+\" \"+self.numberToWords(count)+\" \"+name #self.numberToWords(count)是为了返回 x million里面的x。count就是有几个carry\n",
    "               else:\n",
    "                   result+=\" \"+name\n",
    "        result=result[1:] #循环完了去除开头空格\n",
    "        # 在这个函数中，每次向 result 字符串添加一个新的单词时，都会在其前面加一个空格。\n",
    "        # 这是为了确保所有单词之间都有一个空格。但这样做的副作用是，最初的空格会被添加到 result 的开头。\n",
    "        # 例如，如果 result 是 \" One Billion Two Hundred Thirty Four\"，那么它将以一个空格开头。\n",
    "        # 因此，result = result[1:] 是用来去除这个开头的空格的，使得输出格式正确。\n",
    "        return result\n",
    "    \n",
    "# 空间复杂度也是 O(log N)。\n",
    "\n",
    "# 当然可以，我们可以逐步模拟 `numberToWords` 函数是如何处理输入 `1234567` 的。\n",
    "\n",
    "# 1. **初始化阶段**: \n",
    "#     - `num = 1234567`\n",
    "#     - `result = \"\"`（一个空字符串）\n",
    "\n",
    "# 2. **第一次循环**（针对 `1000000: 'Million'`）:\n",
    "#     - `count = 1234567 // 1000000 = 1`\n",
    "#     - `num = 1234567 % 1000000 = 234567`\n",
    "#     - `count = 1`，而且 `value = 1000000 >= 100`，所以递归调用 `self.numberToWords(count)`，它返回 \"One\"。\n",
    "#     - `result = \" One Million\"`\n",
    "\n",
    "# 3. **第二次循环**（针对 `100000: 'Hundred Thousand'`）:\n",
    "#     - `count = 0`（因为 `num < 100000`）\n",
    "#     - `num = 234567`（没有变化）\n",
    "#     - 什么都不做。\n",
    "\n",
    "# 4. **第三次循环**（针对 `1000: 'Thousand'`）:\n",
    "#     - `count = 234567 // 1000 = 234`\n",
    "#     - `num = 234567 % 1000 = 567`\n",
    "#     - `count = 234`，`value = 1000 >= 100`，所以递归调用 `self.numberToWords(234)`，它返回 \"Two Hundred Thirty Four\"。\n",
    "#     - `result = \" One Million Two Hundred Thirty Four Thousand\"`\n",
    "\n",
    "# 5. **第四次循环**（针对 `100: 'Hundred'`）:\n",
    "#     - `count = 567 // 100 = 5`\n",
    "#     - `num = 567 % 100 = 67`\n",
    "#     - `count = 5`，`value = 100 >= 100`，所以递归调用 `self.numberToWords(5)`，它返回 \"Five\"。\n",
    "#     - `result = \" One Million Two Hundred Thirty Four Thousand Five Hundred\"`\n",
    "\n",
    "# 6. **第五次循环**（针对 `90: 'Ninety'`）:\n",
    "#     - `count = 0`（因为 `num < 90`）\n",
    "#     - `num = 67`（没有变化）\n",
    "#     - 什么都不做。\n",
    "\n",
    "# 7. **第六次循环**（针对 `60: 'Sixty'`）:\n",
    "#     - `count = 67 // 60 = 1`\n",
    "#     - `num = 67 % 60 = 7`\n",
    "#     - `count = 1`，`value < 100`，所以直接添加 \"Sixty\"。\n",
    "#     - `result = \" One Million Two Hundred Thirty Four Thousand Five Hundred Sixty\"`\n",
    "\n",
    "# 8. **第七次循环**（针对 `7: 'Seven'`）:\n",
    "#     - `count = 7 // 7 = 1`\n",
    "#     - `num = 7 % 7 = 0`\n",
    "#     - `count = 1`，`value < 100`，所以直接添加 \"Seven\"。\n",
    "#     - `result = \" One Million Two Hundred Thirty Four Thousand Five Hundred Sixty Seven\"`\n",
    "\n",
    "# 9. **去除开头的空格**:\n",
    "#     - `result = result[1:] = \"One Million Two Hundred Thirty Four Thousand Five Hundred Sixty Seven\"`\n",
    "\n",
    "# 最终输出是 \"One Million Two Hundred Thirty Four Thousand Five Hundred Sixty Seven\"，与预期相符。\n",
    "    \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    D0 = ['Zero','One','Two','Three','Four','Five','Six','Seven','Eight','Nine','Ten','Eleven','Twelve','Thirteen','Fourteen','Fifteen','Sixteen','Seventeen','Eighteen','Nineteen']\n",
    "    D1 = ['Twenty','Thirty','Forty','Fifty','Sixty','Seventy','Eighty','Ninety']\n",
    "    D2 = ['Thousand','Million']\n",
    "    def numberToWords(self, num: int) -> str:\n",
    "        if num < 20: return self.D0[num]\n",
    "        x = [0]*9\n",
    "        for i in range(1,10):\n",
    "            x[-i] = num % 10\n",
    "            num //= 10\n",
    "        #print(x)\n",
    "        s = ''\n",
    "        if num > 0: s = self.D0[num] + ' Billion'\n",
    "        for i in range(3):\n",
    "            a,b,c = x[3*i:3*i+3]\n",
    "            if a > 0: s = ((s+' ') if s else '') + self.D0[a] + ' Hundred'\n",
    "            if b < 2:\n",
    "                if b+c > 0: s = ((s+' ') if s else '') + self.D0[10*b+c]\n",
    "            else:\n",
    "                s = ((s+' ') if s else '') + self.D1[b-2]\n",
    "                if c > 0: s = ((s+' ') if s else '') + self.D0[c]\n",
    "            if i < 2 and a+b+c > 0: s = s + ' ' + self.D2[1-i]\n",
    "        return s\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "singles = [\"\", \"One\", \"Two\", \"Three\", \"Four\", \"Five\", \"Six\", \"Seven\", \"Eight\", \"Nine\"]\n",
    "teens = [\"Ten\", \"Eleven\", \"Twelve\", \"Thirteen\", \"Fourteen\", \"Fifteen\", \"Sixteen\", \"Seventeen\", \"Eighteen\", \"Nineteen\"]\n",
    "tens = [\"\", \"Ten\", \"Twenty\", \"Thirty\", \"Forty\", \"Fifty\", \"Sixty\", \"Seventy\", \"Eighty\", \"Ninety\"]\n",
    "thousands = [\"\", \"Thousand\", \"Million\", \"Billion\"]\n",
    "\n",
    "class Solution:\n",
    "    def numberToWords(self, num: int) -> str:\n",
    "        if num == 0:\n",
    "            return \"Zero\"\n",
    "\n",
    "        def recursion(num: int) -> str:\n",
    "            s = \"\"\n",
    "            if num == 0:\n",
    "                return s\n",
    "            elif num < 10:\n",
    "                s += singles[num] + \" \"\n",
    "            elif num < 20:\n",
    "                s += teens[num - 10] + \" \"\n",
    "            elif num < 100:\n",
    "                s += tens[num // 10] + \" \" + recursion(num % 10)\n",
    "            else:\n",
    "                s += singles[num // 100] + \" Hundred \" + recursion(num % 100)\n",
    "            return s\n",
    "\n",
    "        s = \"\"\n",
    "        unit = int(1e9)\n",
    "        for i in range(3, -1, -1):\n",
    "            curNum = num // unit\n",
    "            if curNum:\n",
    "                num -= curNum * unit\n",
    "                s += recursion(curNum) + thousands[i] + \" \"\n",
    "            unit //= 1000\n",
    "        return s.strip()\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numberToWords(self, num: int) -> str:\n",
    "        bigSep = [\"\", \"Thousand\", \"Million\", \"Billion\"]\n",
    "        Digits = [\"\", \"One\", \"Two\", \"Three\", \"Four\", \"Five\", \"Six\", \"Seven\", \"Eight\", \"Nine\"]\n",
    "        tyTimes = [\"\", \"\", \"Twenty\", \"Thirty\", \"Forty\", \"Fifty\", \"Sixty\", \"Seventy\", \"Eighty\", \"Ninety\"]\n",
    "        teenTimes = [\"Ten\", \"Eleven\", \"Twelve\", \"Thirteen\", \"Fourteen\", \"Fifteen\", \"Sixteen\", \"Seventeen\", \"Eighteen\", \"Nineteen\"]\n",
    "        cnt = 0\n",
    "        res = []\n",
    "        if num == 0: return \"Zero\"\n",
    "        while num > 0:\n",
    "            sub = num % 1000\n",
    "            num //= 1000\n",
    "            if sub == 0: \n",
    "                cnt += 1\n",
    "                continue \n",
    "            tmp = []\n",
    "            if sub >= 100:\n",
    "                tmp.append(Digits[sub // 100])\n",
    "                tmp.append(\"Hundred\")\n",
    "            tyNum = (sub % 100) // 10\n",
    "            if tyNum >= 2:\n",
    "                tmp.append(tyTimes[tyNum])\n",
    "            elif tyNum == 1:\n",
    "                tmp.append(teenTimes[sub % 100 - 10])\n",
    "            lowNum = sub % 10\n",
    "            if lowNum > 0 and tyNum != 1: tmp.append(Digits[lowNum])\n",
    "            if cnt > 0: tmp.append(bigSep[cnt])\n",
    "            res = tmp + res \n",
    "            cnt += 1\n",
    "        return \" \".join(res)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numberToWords(self, num: int) -> str:\n",
    "\n",
    "        # 三个一组 每组单位\n",
    "        if num == 0: return \"Zero\"\n",
    "        singles = [\"\", \"One\", \"Two\", \"Three\", \"Four\", \"Five\", \"Six\", \"Seven\", \"Eight\", \"Nine\"]\n",
    "        teens = [\"Ten\", \"Eleven\", \"Twelve\", \"Thirteen\", \"Fourteen\", \"Fifteen\", \"Sixteen\", \"Seventeen\", \"Eighteen\", \"Nineteen\"]\n",
    "        tens = [\"\", \"Ten\", \"Twenty\", \"Thirty\", \"Forty\", \"Fifty\", \"Sixty\", \"Seventy\", \"Eighty\", \"Ninety\"]\n",
    "        thousands = [\"\", \"Thousand\", \"Million\", \"Billion\"]\n",
    "        # 递归\n",
    "        def num2str(num_):\n",
    "            s = \"\"\n",
    "            if num_ == 0:\n",
    "                return s\n",
    "            if 0< num_ < 10:\n",
    "                return  s + singles[num_] + \" \"\n",
    "            if 10<= num_ < 20:\n",
    "                return s + teens[num_%10] + \" \"\n",
    "            if 20<= num_ < 100:\n",
    "                return s + tens[num_//10] + \" \" + num2str(num_ % 10)\n",
    "            if 100<= num_:\n",
    "                return s + singles[num_//100] + \" Hundred \" + num2str(num_ % 100) \n",
    "        results = \"\"\n",
    "        unit = int(1e9)\n",
    "        # n = len(groups)\n",
    "        for i in range(3, -1, -1):\n",
    "            cur = num // unit\n",
    "            if cur:\n",
    "                results += num2str(cur) + thousands[i] + \" \"\n",
    "                num -= cur * unit\n",
    "            unit //= 1000\n",
    "\n",
    "        return results.strip()\n",
    "\n",
    "\n",
    "            \n",
    "            \n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numberToWords(self, num: int) -> str:\n",
    "        digitMap = ['Zero', 'One', 'Two', 'Three', 'Four', 'Five', 'Six', 'Seven', 'Eight', 'Nine', 'Ten', 'Eleven', 'Twelve', 'Thirteen', 'Fourteen', 'Fifteen', 'Sixteen', 'Seventeen', 'Eighteen', 'Nineteen', 'Twenty']\n",
    "        decadeMap = {2: 'Twenty', 3: 'Thirty', 4: 'Forty', 5: 'Fifty', 6: 'Sixty', 7: 'Seventy', 8: 'Eighty', 9: 'Ninety'}\n",
    "        magMap = {1000: 'Thousand', 1000000: 'Million', 1000000000: 'Billion'}\n",
    "\n",
    "        def toHundreds(n):\n",
    "            ws = []\n",
    "            h = n // 100\n",
    "            n %= 100\n",
    "            if h > 0:\n",
    "                ws.append(digitMap[h])\n",
    "                ws.append('Hundred')\n",
    "            if 0 < n <= 20:\n",
    "                ws.append(digitMap[n])\n",
    "            elif n > 20:\n",
    "                d = n // 10\n",
    "                ws.append(decadeMap[d])\n",
    "                if n % 10 != 0:\n",
    "                    ws.append(digitMap[n % 10])\n",
    "            return ws\n",
    "        \n",
    "        def tran(n, mag):\n",
    "            ws = []\n",
    "            if mag < 1000:\n",
    "                ws.extend(toHundreds(n))\n",
    "            else:\n",
    "                h = n // mag\n",
    "                if h > 0:\n",
    "                    ws.extend(toHundreds(h))\n",
    "                    ws.append(magMap[mag])\n",
    "                ws.extend(tran(n % mag, mag // 1000))\n",
    "            return ws\n",
    "\n",
    "        if num == 0:\n",
    "            return digitMap[0]\n",
    "        \n",
    "        return ' '.join(tran(num, 1000000000))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "s1 = [\"\",\"One\",\"Two\",\"Three\",\"Four\",\"Five\",\"Six\",\"Seven\",\"Eight\",\"Nine\",\"Ten\",\"Eleven\",\"Twelve\",\"Thirteen\",\"Fourteen\",\"Fifteen\",\"Sixteen\",\"Seventeen\",\"Eighteen\",\"Nineteen\"]\n",
    "s2 = [\"\",\"\",\"Twenty\",\"Thirty\",\"Forty\",\"Fifty\",\"Sixty\",\"Seventy\",\"Eighty\",\"Ninety\"]\n",
    "\n",
    "class Solution:\n",
    "    def numberToWords(self, num: int) -> str:\n",
    "        if num == 0:return \"Zero\"\n",
    "        def helper(num):\n",
    "            if num == 0:return \"\"\n",
    "            if num < 20:return \" \" + s1[num]\n",
    "            if num < 100:return \" \" + s2[num//10] + helper(num%10)\n",
    "            if num < 1000:return \" \" + s1[num//100] + \" Hundred\" + helper(num%100)\n",
    "            for i,j in enumerate([\"Thousand\", \"Million\", \"Billion\"], 1):\n",
    "                if num < 1000 ** (i+1):\n",
    "                    return helper(num // 1000**i) + \" \" + j + helper(num % 1000**i)\n",
    "        return helper(num).strip()\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numberToWords(self, num: int) -> str:\n",
    "        def lt273(num):\n",
    "            def one_parse(s):\n",
    "                if s=='0':return ''\n",
    "                if s=='1':return 'One'\n",
    "                if s=='2':return 'Two'\n",
    "                if s=='3':return 'Three'\n",
    "                if s=='4':return 'Four'\n",
    "                if s=='5':return 'Five'\n",
    "                if s=='6':return 'Six'\n",
    "                if s=='7':return 'Seven'\n",
    "                if s=='8':return 'Eight'\n",
    "                if s=='9':return 'Nine'\n",
    "            def two_parse(s):\n",
    "                if s[0]=='0':return one_parse(s[1])\n",
    "                if s[0]=='1':\n",
    "                    if s=='10':return 'Ten'\n",
    "                    if s=='11':return 'Eleven'\n",
    "                    if s=='12':return 'Twelve'\n",
    "                    if s=='13':return 'Thirteen'\n",
    "                    if s=='14':return 'Fourteen'\n",
    "                    if s=='15':return 'Fifteen'\n",
    "                    if s=='16':return 'Sixteen'\n",
    "                    if s=='17':return 'Seventeen'\n",
    "                    if s=='18':return 'Eighteen'\n",
    "                    if s=='19':return 'Nineteen'\n",
    "                if s[0]=='2':\n",
    "                    if s=='20':return 'Twenty'\n",
    "                    return 'Twenty'+' '+one_parse(s[1])\n",
    "                if s[0]=='3':\n",
    "                    if s=='30':return 'Thirty'\n",
    "                    return 'Thirty'+' '+one_parse(s[1])\n",
    "                if s[0]=='4':\n",
    "                    if s=='40':return 'Forty'\n",
    "                    return 'Forty'+' '+one_parse(s[1])\n",
    "                if s[0]=='5':\n",
    "                    if s=='50':return 'Fifty'\n",
    "                    return 'Fifty'+' '+one_parse(s[1])\n",
    "                if s[0]=='6':\n",
    "                    if s=='60':return 'Sixty'\n",
    "                    return 'Sixty'+' '+one_parse(s[1])\n",
    "                if s[0]=='7':\n",
    "                    if s=='70':return 'Seventy'\n",
    "                    return 'Seventy'+' '+one_parse(s[1])\n",
    "                if s[0]=='8':\n",
    "                    if s=='80':return 'Eighty'\n",
    "                    return 'Eighty'+' '+one_parse(s[1])\n",
    "                if s[0]=='9':\n",
    "                    if s=='90':return 'Ninety'\n",
    "                    return 'Ninety'+' '+one_parse(s[1])\n",
    "            def three_parse(s):\n",
    "                if len(s)==1:return one_parse(s)\n",
    "                elif len(s)==2:return two_parse(s)\n",
    "                if s[0]=='0':return two_parse(s[1:])\n",
    "                return one_parse(s[0])+' '+'Hundred'+' '+two_parse(s[1:])\n",
    "            if num==0:return 'Zero'\n",
    "            s=str(num)\n",
    "            scales=['','Thousand','Million','Billion']\n",
    "            temp,remain,idx=[],len(s)%3,0\n",
    "            if remain:\n",
    "                temp.append(s[idx:remain])\n",
    "                idx+=remain\n",
    "            while idx<len(s):\n",
    "                temp.append(s[idx:idx+3])\n",
    "                idx+=3\n",
    "\n",
    "            num_scale=len(temp)\n",
    "            res=''\n",
    "            for i in range(num_scale):\n",
    "                tt=three_parse(temp[i])\n",
    "                if tt:res=res+' '+tt+' '+scales[num_scale-1-i]\n",
    "            res_=[]\n",
    "            for ch in res:\n",
    "                if ch==' ':continue\n",
    "                if ord('A')<=ord(ch)<=ord('Z'):\n",
    "                    res_.append(' ')\n",
    "                res_.append(ch)\n",
    "            res_=''.join(res_)\n",
    "            return res_.strip()\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "        return lt273(num)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numberToWords(self, num: int) -> str:\n",
    "        singles = [\"\", \"One\", \"Two\", \"Three\", \"Four\", \"Five\", \"Six\", \"Seven\", \"Eight\", \"Nine\"]\n",
    "        teens = [\"Ten\", \"Eleven\", \"Twelve\", \"Thirteen\", \"Fourteen\", \"Fifteen\", \"Sixteen\", \"Seventeen\", \"Eighteen\",  \"Nineteen\"]\n",
    "        tens = [\"\", \"Ten\", \"Twenty\", \"Thirty\", \"Forty\", \"Fifty\", \"Sixty\", \"Seventy\", \"Eighty\", \"Ninety\"]\n",
    "        thousands = [\"\", \"Thousand\", \"Million\", \"Billion\"]\n",
    "    \n",
    "       \n",
    "        def recursion(num):\n",
    "            if num == 0:\n",
    "                return ''\n",
    "            elif num <10:\n",
    "                return singles[num]  +' '\n",
    "            elif num < 20:\n",
    "                return teens[num-10] +' '\n",
    "            elif num < 100:\n",
    "                return tens[num//10] +' '+recursion(num%10)\n",
    "            else:\n",
    "                return singles[num//100] +' Hundred ' + recursion(num%100)\n",
    "            \n",
    "        if num == 0:\n",
    "            return 'Zero'\n",
    "        \n",
    "        unit = 10**9\n",
    "        s = ''\n",
    "        for i in range(3,-1,-1):\n",
    "            curr_num = num // unit\n",
    "            if curr_num:\n",
    "                #print(f'this is cur {curr_num}')\n",
    "                s += recursion(curr_num)  + thousands[i] +' '\n",
    "                num = num - curr_num * unit\n",
    "            \n",
    "            unit //= 1000\n",
    "        return s.strip()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numberToWords(self, num: int) -> str:\n",
    "        p1 = [\"\", \"One\", \"Two\", \"Three\", \"Four\", \"Five\", \"Six\", \"Seven\", \"Eight\", \"Nine\"]\n",
    "        p2 = [\"Eleven\", \"Twelve\", \"Thirteen\", \"Fourteen\", \"Fifteen\", \"Sixteen\", \"Seventeen\", \"Eighteen\", \"Nineteen\"]\n",
    "        p3 = [\"Ten\", \"Twenty\", \"Thirty\", \"Forty\", \"Fifty\", \"Sixty\", \"Seventy\", \"Eighty\", \"Ninety\"]\n",
    "        if num == 0:\n",
    "            return \"Zero\"\n",
    "\n",
    "        def _2str(num):\n",
    "            if num < 10: return p1[num]\n",
    "            if num % 10 == 0:\n",
    "                return p3[num // 10 - 1]\n",
    "            if 11 <= num < 20:\n",
    "                return p2[num - 11]\n",
    "\n",
    "            return p3[num // 10 - 1] + ' ' + p1[num % 10]\n",
    "\n",
    "\n",
    "        def _3str(num):\n",
    "            if num < 100: return _2str(num)\n",
    "\n",
    "            return p1[num // 100] + \" Hundred \" + _2str(num % 100)\n",
    "        \n",
    "        ans = \"\"\n",
    "\n",
    "        if num < 1000:\n",
    "            ans = _3str(num)\n",
    "\n",
    "        if 1000 <= num < 1000000:\n",
    "\n",
    "            ans = _3str(num // 1000) + \" Thousand \" + _3str(num % 1000)\n",
    "\n",
    "        if 1000000 <= num < 1000000000:\n",
    "            s1 = _3str(num // 1000000) + \" Million \"\n",
    "            s2 = \"\"\n",
    "            if (num // 1000) % 1000:\n",
    "                s2 = _3str((num // 1000) % 1000) + \" Thousand \"\n",
    "            s3 = _3str(num % 1000)\n",
    "\n",
    "            ans = s1 + s2 + s3\n",
    "\n",
    "        # 1 000 000 007\n",
    "        if num >= 1000000000:\n",
    "            s1 = _3str(num // 1000000000) + \" Billion \"\n",
    "            s2 = \"\"\n",
    "            if (num // 1000000) % 1000:\n",
    "                s2 = _3str((num // 1000000) % 1000) + \" Million \"\n",
    "            s3 = \"\"\n",
    "            if (num // 1000) % 1000:\n",
    "                s3 = _3str((num // 1000) % 1000) + \" Thousand \"\n",
    "            s4 = _3str(num % 1000)\n",
    "            ans = s1 + s2 + s3 + s4\n",
    "\n",
    "        v = ans.split(' ')\n",
    "        return ' '.join(i for i in v if i)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numberToWords(self, num: int) -> str:\n",
    "        if num == 0:\n",
    "            return 'Zero'\n",
    "        num_eng = {'0': '', '1': ' One', '2': ' Two', '3': ' Three', '4': ' Four', '5': ' Five', '6': ' Six', '7': ' Seven', '8': ' Eight', '9': ' Nine'}\n",
    "        num_eng_teen = {'0': ' Ten', '1': ' Eleven', '2': ' Twelve', '3': ' Thirteen', '4': ' Fourteen', '5': ' Fifteen', '6': ' Sixteen', '7': ' Seventeen', '8': ' Eighteen', '9': ' Nineteen'}\n",
    "        num_eng_ty = {'0': '', '2': ' Twenty', '3': ' Thirty', '4': ' Forty', '5': ' Fifty', '6': ' Sixty', '7': ' Seventy', '8': ' Eighty', '9': ' Ninety'}\n",
    "        digit = {0: '', 1: ' Thousand', 2: ' Million', 3: ' Billion'}\n",
    "        num = str(num)\n",
    "        num_List = []\n",
    "        n = len(num)\n",
    "        i = n\n",
    "        while i > 3:\n",
    "            num_List.append(num[i - 3: i])\n",
    "            i -= 3\n",
    "        num_List.append(num[:i])\n",
    "        m = len(num_List)\n",
    "        ans = ''\n",
    "        for j in range(m):\n",
    "            if j == m - 1:\n",
    "                if len(num_List[j]) == 1:\n",
    "                    ans = num_eng[num_List[j]] + digit[j] + ans\n",
    "                    break\n",
    "                elif len(num_List[j]) == 2:\n",
    "                    if num_List[j][0] == '1':\n",
    "                        ans = num_eng_teen[num_List[j][1]] + digit[j] + ans\n",
    "                    else:\n",
    "                        ans = num_eng_ty[num_List[j][0]] + num_eng[num_List[j][1]] + digit[j] + ans\n",
    "                    break\n",
    "            if num_List[j] == '000':\n",
    "                continue\n",
    "            a = ''\n",
    "            if num_List[j][0] != '0':\n",
    "                a += num_eng[num_List[j][0]] + ' Hundred'\n",
    "            if num_List[j][1] == '1':\n",
    "                a += num_eng_teen[num_List[j][2]] + digit[j]\n",
    "            else:\n",
    "                a += num_eng_ty[num_List[j][1]] + num_eng[num_List[j][2]] + digit[j]\n",
    "            ans = a + ans\n",
    "        return ans[1:]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numberToWords(self, num: int) -> str:\n",
    "        ones = [\"\", \"One\", \"Two\", \"Three\", \"Four\", \"Five\", \"Six\", \"Seven\", \"Eight\", \"Nine\"]\n",
    "        teens = [\"Ten\", \"Eleven\", \"Twelve\", \"Thirteen\", \"Fourteen\", \"Fifteen\", \"Sixteen\", \"Seventeen\", \"Eighteen\", \"Nineteen\"]\n",
    "        tens = [\"\", \"Ten\", \"Twenty\", \"Thirty\", \"Forty\", \"Fifty\", \"Sixty\", \"Seventy\", \"Eighty\", \"Ninety\"]\n",
    "        thousands = [\"\", \"Thousand\", \"Million\", \"Billion\", \"Trillion\"]\n",
    "        def helper(num, idx):\n",
    "            if num == 0:\n",
    "                return \"\"\n",
    "            elif num < 10:\n",
    "                return ones[num] + \" \"\n",
    "            elif num < 20:\n",
    "                return teens[num - 10] + \" \"\n",
    "            elif num < 100:\n",
    "                return tens[num // 10] + \" \" + helper(num % 10, idx)\n",
    "            else:\n",
    "                return ones[num // 100] + \" Hundred \" + helper(num % 100, idx)\n",
    "\n",
    "        if num == 0:\n",
    "            return \"Zero\"\n",
    "\n",
    "        result = \"\"\n",
    "        idx = 0\n",
    "        while num > 0:\n",
    "            if num % 1000 != 0:\n",
    "                result = helper(num % 1000, idx) + thousands[idx] + \" \" + result\n",
    "            num //= 1000\n",
    "            idx += 1\n",
    "\n",
    "        return result.strip()\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numberToWords(self, num: int) -> str:\n",
    "        if num == 0:\n",
    "            return \"Zero\"\n",
    "        \n",
    "        def one(num):\n",
    "            switcher = {\n",
    "                1: 'One',\n",
    "                2: 'Two',\n",
    "                3: 'Three',\n",
    "                4: 'Four',\n",
    "                5: 'Five',\n",
    "                6: 'Six',\n",
    "                7: 'Seven',\n",
    "                8: 'Eight',\n",
    "                9: 'Nine'\n",
    "            }\n",
    "            return switcher.get(num)\n",
    "        \n",
    "        def two_less_20(num):\n",
    "            switcher = {\n",
    "                10: 'Ten',\n",
    "                11: 'Eleven',\n",
    "                12: 'Twelve',\n",
    "                13: 'Thirteen',\n",
    "                14: 'Fourteen',\n",
    "                15: 'Fifteen',\n",
    "                16: 'Sixteen',\n",
    "                17: 'Seventeen',\n",
    "                18: 'Eighteen',\n",
    "                19: 'Nineteen'\n",
    "            }\n",
    "            return switcher.get(num)\n",
    "        \n",
    "        def ten(num):\n",
    "            switcher = {\n",
    "                2: 'Twenty',\n",
    "                3: 'Thirty',\n",
    "                4: 'Forty',\n",
    "                5: 'Fifty',\n",
    "                6: 'Sixty',\n",
    "                7: 'Seventy',\n",
    "                8: 'Eighty',\n",
    "                9: 'Ninety'\n",
    "            }\n",
    "            return switcher.get(num)\n",
    "        \n",
    "        def two(num):\n",
    "            if not num:\n",
    "                return ''\n",
    "            elif num < 10:\n",
    "                return one(num)\n",
    "            elif num < 20:\n",
    "                return two_less_20(num)\n",
    "            else:\n",
    "                tenner = num // 10\n",
    "                rest = num - tenner * 10\n",
    "                return ten(tenner) + ' ' + one(rest) if rest else ten(tenner)\n",
    "        \n",
    "        def three(num):\n",
    "            hundred = num // 100\n",
    "            rest = num - hundred * 100\n",
    "            if hundred and rest:\n",
    "                return one(hundred) + ' Hundred ' + two(rest)\n",
    "            elif not hundred and rest:\n",
    "                return two(rest)\n",
    "            elif hundred and not rest:\n",
    "                return one(hundred) + ' Hundred'\n",
    "        \n",
    "        billion = num // 1000000000\n",
    "        million = (num - billion * 1000000000) // 1000000\n",
    "        thousand = (num - billion * 1000000000 - million * 1000000) // 1000\n",
    "        remainder = num - billion * 1000000000 - million * 1000000 - thousand * 1000\n",
    "        \n",
    "        result = ''\n",
    "        if billion:\n",
    "            result += three(billion) + ' Billion'\n",
    "        if million:\n",
    "            if result:\n",
    "                result += ' '\n",
    "            result += three(million) + ' Million'\n",
    "        if thousand:\n",
    "            if result:\n",
    "                result += ' '\n",
    "            result += three(thousand) + ' Thousand'\n",
    "        if remainder:\n",
    "            if result:\n",
    "                result += ' '\n",
    "            result += three(remainder)\n",
    "        \n",
    "        return result"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numberToWords(self, num: int) -> str:\n",
    "        if num==0:\n",
    "            return 'Zero'\n",
    "        num1 = ['Zero','One','Two','Three','Four','Five','Six',\n",
    "       'Seven','Eight','Nine','Ten','Eleven','Twelve',\n",
    "       'Thirteen','Fourteen','Fifteen','Sixteen',\n",
    "       'Seventeen','Eighteen','Nineteen']\n",
    "        num2 = [0,0,'Twenty','Thirty','Forty','Fifty','Sixty',\n",
    "            'Seventy','Eighty','Ninety']\n",
    "        \n",
    "        # 100以内转英文\n",
    "        def n2w(n):\n",
    "            if n > 0:\n",
    "                if n < 20:\n",
    "                    word.append(num1[n])\n",
    "                else:\n",
    "                    word.append(num2[n//10])\n",
    "                    if n%10 != 0:\n",
    "                        word.append(num1[n%10])\n",
    "        \n",
    "        # 1000以内转英文\n",
    "        def hun(n):\n",
    "            if n >= 100:\n",
    "                word.append(num1[n//100])\n",
    "                word.append('Hundred')\n",
    "            n2w(n%100)\n",
    "        n = num\n",
    "        word = []\n",
    "        a = n % 1000  # 个十百位\n",
    "        b = (n//1000) % 1000  # 个十百千\n",
    "        c = (n//1000000) % 1000  #个十百m\n",
    "        d = n // 1000000000    # 个十百b\n",
    "        \n",
    "        if d > 0:\n",
    "            hun(d)\n",
    "            word.append('Billion')\n",
    "        if c > 0 :\n",
    "            hun(c)\n",
    "            word.append('Million')\n",
    "        if b > 0:\n",
    "            hun(b)\n",
    "            word.append('Thousand')\n",
    "        if a > 0 :\n",
    "            hun(a)\n",
    "        return ' '.join(word)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numberToWords(self, num: int) -> str:\n",
    "        singles = [\"\", \"One\", \"Two\", \"Three\", \"Four\", \"Five\", \"Six\", \"Seven\", \"Eight\", \"Nine\"]\n",
    "        teens = [\"Ten\", \"Eleven\", \"Twelve\", \"Thirteen\", \"Fourteen\", \"Fifteen\", \"Sixteen\", \"Seventeen\", \"Eighteen\", \"Nineteen\"]\n",
    "        tens = [\"\", \"Ten\", \"Twenty\", \"Thirty\", \"Forty\", \"Fifty\", \"Sixty\", \"Seventy\", \"Eighty\", \"Ninety\"]\n",
    "        thousands = [\"\", \"Thousand\", \"Million\", \"Billion\"]\n",
    "\n",
    "\n",
    "        if num == 0:\n",
    "            return \"Zero\"\n",
    "\n",
    "        def toEnglish(num: int) -> str:\n",
    "            s = \"\"\n",
    "            if num >= 100:\n",
    "                s += singles[num // 100] + \" Hundred \"\n",
    "                num %= 100\n",
    "            if num >= 20:\n",
    "                s += tens[num // 10] + \" \"\n",
    "                num %= 10\n",
    "            if 0 < num < 10:\n",
    "                s += singles[num] + \" \"\n",
    "            elif num >= 10:\n",
    "                s += teens[num - 10] + \" \"\n",
    "            return s\n",
    "\n",
    "        s = \"\"\n",
    "        unit = int(1e9)\n",
    "        for i in range(3, -1, -1):\n",
    "            curNum = num // unit\n",
    "            if curNum:\n",
    "                num -= curNum * unit\n",
    "                s += toEnglish(curNum) + thousands[i] + \" \"\n",
    "            unit //= 1000\n",
    "        return s.strip()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "singles=[\"\",\"One\",\"Two\",\"Three\",\"Four\",\"Five\",\"Six\",\"Seven\",\"Eight\",\"Nine\"]\n",
    "teens=[\"Ten\",\"Eleven\",\"Twelve\",\"Thirteen\",\"Fourteen\",\"Fifteen\",\"Sixteen\",\"Seventeen\",\"Eighteen\",\"Nineteen\"]\n",
    "tens=[\",\",\"Ten\",\"Twenty\",\"Thirty\",\"Forty\",\"Fifty\",\"Sixty\",\"Seventy\",\"Eighty\",\"Ninety\"]\n",
    "thousands=[\"\",\"Thousand\",\"Million\",\"Billion\"]\n",
    "class Solution:\n",
    "    def recursion(self,num:int)->str:\n",
    "        s=\"\"\n",
    "        if num==0:return s\n",
    "        elif num<10:\n",
    "            s+=singles[num]+\" \"\n",
    "        elif num<20:\n",
    "            s+=teens[num%10]+\" \"\n",
    "        elif num<100:\n",
    "            s+=tens[num//10]+\" \"+self.recursion(num%10)\n",
    "        else:\n",
    "            s+=singles[num//100]+\" Hundred \"+self.recursion(num%100)\n",
    "        return s\n",
    "    def numberToWords(self, num: int) -> str:\n",
    "        if num==0:return \"Zero\"\n",
    "        s=\"\"\n",
    "        unit=int(1e9)\n",
    "        for i in range(3,-1,-1):\n",
    "            curNum=num//unit\n",
    "            if curNum:\n",
    "                num-=curNum*unit\n",
    "                s+=self.recursion(curNum)+thousands[i]+\" \"\n",
    "            unit//=1000\n",
    "        return s.strip()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def __init__(self):\n",
    "        self.nt = [\"Zero\", \"One\", \"Two\", \"Three\", \"Four\", \"Five\", \"Six\", \"Seven\", \"Eight\", \"Nine\", \"Ten\", \"Eleven\", \"Twelve\",\n",
    "        \"Thirteen\", \"Fourteen\", \"Fifteen\", \"Sixteen\", \"Seventeen\", \"Eighteen\", \"Nineteen\"]\n",
    "        self.tens = [\"\", \"\", \"Twenty\", \"Thirty\", \"Forty\", \"Fifty\", \"Sixty\", \"Seventy\", \"Eighty\", \"Ninety\"]\n",
    "        self.t = [\"Thousand\", \"Million\", \"Billion\"]\n",
    "\n",
    "    def numberToWords(self, num: int) -> str:\n",
    "        def helper(num) -> list[str]:\n",
    "            if num < 20:\n",
    "                return [self.nt[num]]\n",
    "            elif num < 100:\n",
    "                res = [self.tens[num//10]]\n",
    "                if num % 10:\n",
    "                    res += helper(num % 10)\n",
    "                return res\n",
    "            elif num < 1000:\n",
    "                res = [self.nt[num//100], \"Hundred\"]\n",
    "                if num % 100:\n",
    "                    res += helper(num%100)\n",
    "                return res\n",
    "            for p, w in enumerate(self.t, 1):\n",
    "                if num < 1000 ** (p + 1):\n",
    "                    return helper(num // 1000 ** p) + [w] + helper(num % 1000 ** p) if num % 1000 ** p else helper(num // 1000 ** p) + [w]\n",
    "        return \" \".join(helper(num))\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "singles = ['', 'One', 'Two', 'Three', 'Four', 'Five', 'Six', 'Seven', 'Eight', 'Nine', 'Ten', 'Eleven', 'Twelve', 'Thirteen', 'Fourteen', 'Fifteen', 'Sixteen', 'Seventeen', 'Eighteen', 'Nineteen']\n",
    "tens = ['', '', 'Twenty', 'Thirty', 'Forty', 'Fifty', 'Sixty', 'Seventy', 'Eighty', 'Ninety']\n",
    "levels = ['', 'Thousand', 'Million', 'Billion']\n",
    "\n",
    "class Solution:\n",
    "    def numberToWords(self, num: int) -> str:\n",
    "        if num == 0:\n",
    "            return 'Zero'\n",
    "\n",
    "        def converte(n):\n",
    "            if n >= 100:\n",
    "                q, n = divmod(n, 100)\n",
    "                res.append(f'{singles[q]} Hundred')\n",
    "            if n >= 20:\n",
    "                q, n = divmod(n, 10)\n",
    "                res.append(tens[q])\n",
    "            if n > 0:\n",
    "                res.append(singles[n])\n",
    "\n",
    "        res = []\n",
    "        if num >= 1000000000:\n",
    "            n, num = divmod(num, 1000000000)\n",
    "            converte(n)\n",
    "            res.append(levels[-1])\n",
    "        if num >= 1000000:\n",
    "            n, num = divmod(num, 1000000)\n",
    "            converte(n)\n",
    "            res.append(levels[-2])\n",
    "        if num >= 1000:\n",
    "            n, num = divmod(num, 1000)\n",
    "            converte(n)\n",
    "            res.append(levels[-3])\n",
    "        if num > 0:\n",
    "            converte(num)\n",
    "        return ' '.join(res)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "singles = [\"\", \"One\", \"Two\", \"Three\", \"Four\", \"Five\", \"Six\", \"Seven\", \"Eight\", \"Nine\"]\n",
    "teens = [\"Ten\", \"Eleven\", \"Twelve\", \"Thirteen\", \"Fourteen\", \"Fifteen\", \"Sixteen\", \"Seventeen\", \"Eighteen\", \"Nineteen\"]\n",
    "tens = [\"\", \"Ten\", \"Twenty\", \"Thirty\", \"Forty\", \"Fifty\", \"Sixty\", \"Seventy\", \"Eighty\", \"Ninety\"]\n",
    "thousands = {1:\"\", 1000:\"Thousand\", 1000000:\"Million\", 1000000000:\"Billion\"}\n",
    "\n",
    "class Solution:\n",
    "    def numberToWords(self, num: int) -> str:\n",
    "        ans=''\n",
    "        x=1000000000\n",
    "        if num==0:\n",
    "            return 'Zero'\n",
    "        while x>0:\n",
    "            y=num//x\n",
    "            h,t,s=y//100,(y%100//10),y%10\n",
    "            if h>0:\n",
    "                ans+=singles[h]+' Hundred '\n",
    "            if t>1:\n",
    "                ans+=tens[t]+' '\n",
    "            if t==1:\n",
    "                ans+=teens[s]+' '\n",
    "            elif s>0:\n",
    "                ans+=singles[s]+' '\n",
    "            if y>0:\n",
    "                ans+=thousands[x]+' '\n",
    "            num=num%x\n",
    "            x//=1000\n",
    "        # return ans[:-1 if ans[-2]!=' ' else -2]\n",
    "        return ans.strip()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "singles = ['', 'One', 'Two', 'Three', 'Four', 'Five', 'Six', 'Seven', 'Eight', 'Nine', 'Ten', 'Eleven', 'Twelve', 'Thirteen', 'Fourteen', 'Fifteen', 'Sixteen', 'Seventeen', 'Eighteen', 'Nineteen']\n",
    "tens = ['', '', 'Twenty', 'Thirty', 'Forty', 'Fifty', 'Sixty', 'Seventy', 'Eighty', 'Ninety']\n",
    "levels = ['', 'Thousand', 'Million', 'Billion']\n",
    "\n",
    "class Solution:\n",
    "    def numberToWords(self, num: int) -> str:\n",
    "        if num == 0:\n",
    "            return 'Zero'\n",
    "\n",
    "        def converte(n):\n",
    "            if n >= 100:\n",
    "                q, n = divmod(n, 100)\n",
    "                res.append(f'{singles[q]} Hundred')\n",
    "            if n >= 20:\n",
    "                q, n = divmod(n, 10)\n",
    "                res.append(tens[q])\n",
    "            if n > 0:\n",
    "                res.append(singles[n])\n",
    "\n",
    "        res = []\n",
    "        if num >= 1000000000:\n",
    "            n, num = divmod(num, 1000000000)\n",
    "            converte(n)\n",
    "            res.append(levels[-1])\n",
    "        if num >= 1000000:\n",
    "            n, num = divmod(num, 1000000)\n",
    "            converte(n)\n",
    "            res.append(levels[-2])\n",
    "        if num >= 1000:\n",
    "            n, num = divmod(num, 1000)\n",
    "            converte(n)\n",
    "            res.append(levels[-3])\n",
    "        if num > 0:\n",
    "            converte(num)\n",
    "        return ' '.join(res)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "name20 = [\"Zero\", \"One\", \"Two\", \"Three\", \"Four\", \"Five\", \"Six\", \"Seven\", \"Eight\", \"Nine\", \"Ten\", \"Eleven\", \"Twelve\", \"Thirteen\", \"Fourteen\", \"Fifteen\", \"Sixteen\", \"Seventeen\", \"Eighteen\", \"Nineteen\"]\n",
    "name10 = [\"\", \"\", \"Twenty\", \"Thirty\", \"Forty\", \"Fifty\", \"Sixty\", \"Seventy\", \"Eighty\", \"Ninety\"]\n",
    "name1000 = [\"\", \"Thousand\", \"Million\", \"Billion\"]\n",
    "class Solution:\n",
    "    def numberToWords(self, num: int) -> str:\n",
    "        if num < 20:\n",
    "            return name20[num]\n",
    "        elif num < 100:\n",
    "            return name10[num // 10] + (' ' + name20[num % 10] if num % 10 else '')\n",
    "        elif num < 1000:\n",
    "            return name20[num // 100] + ' Hundred' + (' ' + self.numberToWords(num % 100) if num % 100 else '')\n",
    "        else:\n",
    "            n1000 = 0\n",
    "            ans = ''\n",
    "            while num > 0:\n",
    "                a = num % 1000\n",
    "                if a > 0:\n",
    "                    if ans:\n",
    "                        ans = ' ' + ans\n",
    "                    ans = self.numberToWords(a) + (' ' + name1000[n1000] if n1000 > 0 else '') + ans\n",
    "                n1000 += 1\n",
    "                num //= 1000\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numberToWords(self, num: int) -> str:\n",
    "        if num == 0:\n",
    "            return \"Zero\"\n",
    "        ged = ['One',\"Two\",\"Three\",\"Four\",\"Five\",\"Six\",\"Seven\",\"Eight\",\"Nine\"]\n",
    "        shd = ['Eleven',\"Twelve\",\"Thirteen\",'Fourteen','Fifteen','Sixteen','Seventeen','Eighteen','Nineteen']\n",
    "        shid = [\"Twenty\",'Thirty','Forty','Fifty','Sixty','Seventy','Eighty','Ninety']\n",
    "        ge = 0\n",
    "        shi = 0\n",
    "        bai = 0\n",
    "        qian = 0\n",
    "        baiwan = 0\n",
    "        shiyi = 0\n",
    "        dang = \"ge\"\n",
    "        qit = 1\n",
    "        bait = 10\n",
    "        shiyit = 10\n",
    "        orinum = num\n",
    "        while num>0:\n",
    "            x = num % 10\n",
    "            num = num // 10\n",
    "            if dang == \"ge\":\n",
    "                ge = x\n",
    "                dang = \"shi\"\n",
    "            elif dang == \"shi\":\n",
    "                shi = x\n",
    "                dang = \"bai\"\n",
    "            elif dang == \"bai\":\n",
    "                bai = x\n",
    "                dang = \"qian\"\n",
    "            elif dang == \"qian\":\n",
    "                if qit <= 100:\n",
    "                    qian = qit*x+qian\n",
    "                    qit *= 10\n",
    "                else:\n",
    "                    baiwan = x\n",
    "                    dang = \"baiwan\"\n",
    "            elif dang == \"baiwan\":\n",
    "                if bait <= 100:\n",
    "                    baiwan = bait*x+baiwan\n",
    "                    bait *= 10\n",
    "                else:\n",
    "                    shiyi = x\n",
    "                    dang = \"shiyi\"\n",
    "            else:\n",
    "                shiyi = shiyit * x + shiyi\n",
    "                shiyit *= 10\n",
    "        str = \"\"\n",
    "        if bai > 0:\n",
    "            str = ged[bai-1]+\" \"+\"Hundred \"\n",
    "        if shi > 0:\n",
    "            if shi == 1:\n",
    "                if ge == 0:\n",
    "                    str += \"Ten\"\n",
    "                else:\n",
    "                    str += shd[ge-1]\n",
    "            else:\n",
    "                str += shid[shi-2] + \" \"\n",
    "        if ge > 0 and shi != 1:\n",
    "            str += ged[ge-1]\n",
    "        if orinum < 1000:\n",
    "            return str.strip()\n",
    "        else:\n",
    "            if qian > 0:\n",
    "                str = self.numberToWords(qian) + \" Thousand \" + str\n",
    "            if baiwan > 0:\n",
    "                str = self.numberToWords(baiwan) + \" Million \" + str\n",
    "            if shiyi > 0:\n",
    "                str = self.numberToWords(shiyi) + \" Billion \" + str\n",
    "            return str.strip()  "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numberToWords(self, num: int) -> str:\n",
    "        if num == 0:\n",
    "            return 'Zero'\n",
    "        singles = [\"\", \"One\", \"Two\", \"Three\", \"Four\", \"Five\", \"Six\", \"Seven\", \"Eight\", \"Nine\"]\n",
    "        teens = [\"Ten\", \"Eleven\", \"Twelve\", \"Thirteen\", \"Fourteen\", \"Fifteen\", \"Sixteen\", \"Seventeen\", \"Eighteen\", \"Nineteen\"]\n",
    "        tens = [\"\", \"Ten\", \"Twenty\", \"Thirty\", \"Forty\", \"Fifty\", \"Sixty\", \"Seventy\", \"Eighty\", \"Ninety\"]\n",
    "        thousands = [\"\", \"Thousand\", \"Million\", \"Billion\"]\n",
    "        digits = [0, 0, 0, 0] + [int(c) for c in str(num)]\n",
    "        ans = []\n",
    "        n1000 = 0\n",
    "        while num > 0:\n",
    "            n100 = digits[-n1000 * 3 - 3]\n",
    "            n10 = digits[-n1000 * 3 - 2]\n",
    "            n1 = digits[-n1000 * 3 - 1]\n",
    "            num //= 1000\n",
    "            t = []\n",
    "            if n100 > 0:\n",
    "                t += [singles[n100], 'Hundred']\n",
    "            if n10 > 1:\n",
    "                t += [tens[n10]]\n",
    "            if n10 == 1:\n",
    "                if n1 == 0:\n",
    "                    t += [tens[n10]]\n",
    "                else:\n",
    "                    t += [teens[n1]]\n",
    "            elif n1 > 0:\n",
    "                t += [singles[n1]]\n",
    "            if n1000 > 0 and t:\n",
    "                t += [thousands[n1000]]\n",
    "            n1000 += 1\n",
    "            ans = t + ans\n",
    "        return ' '.join(ans)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def __init__(self):\n",
    "        self.n={1:'One',2:'Two',3:'Three',4:'Four',5:'Five',6:'Six',7:'Seven',8:'Eight',9:'Nine'}\n",
    "        self.teen={10:'Ten',11:'Eleven',12:'Twelve',13:'Thirteen',14:'Fourteen',15:'Fifteen',16:'Sixteen',17:'Seventeen',18:'Eighteen',19:'Nineteen'}\n",
    "        self.ty={\n",
    "            2:'Twenty',3:'Thirty',4:'Forty',5:'Fifty',6:'Sixty',7:'Seventy',8:'Eighty',9:'Ninety'}\n",
    "    def helper1(self,num):\n",
    "        if num<10:\n",
    "            return self.n[num]\n",
    "        elif num<20:\n",
    "            return self.teen[num]\n",
    "    def helper2(self,num):\n",
    "        if num%10==0:\n",
    "            return self.ty[num//10]\n",
    "        else:\n",
    "            first=self.ty[num//10]\n",
    "            second=self.n[num%10]\n",
    "            return first+' '+second\n",
    "    def helper(self,num):#100-1000\n",
    "        if num<20:\n",
    "            return self.helper1(num)\n",
    "        elif num<100:\n",
    "            return self.helper2(num)\n",
    "        else:\n",
    "            if num%100==0:\n",
    "                return self.n[num//100]+' Hundred'\n",
    "            else:\n",
    "                first=self.n[num//100]+' Hundred'\n",
    "                rest=num%100\n",
    "                if rest<20:\n",
    "                    rest=self.helper1(num%100)\n",
    "                else:\n",
    "                    rest=self.helper2(num%100)\n",
    "                return first+' '+rest\n",
    "    def numberToWords(self, num: int) -> str:\n",
    "        if num==0:\n",
    "            return 'Zero'\n",
    "        billion=num//1000000000\n",
    "        million=(num-billion*1000000000)//1000000\n",
    "        thousand=(num - billion * 1000000000 - million * 1000000) // 1000\n",
    "        rest=num - billion * 1000000000 - million * 1000000-thousand*1000\n",
    "        res=[]\n",
    "        if billion:\n",
    "            res.append(self.helper(billion) +' Billion')\n",
    "        if million:\n",
    "            res.append(self.helper(million)+' Million')\n",
    "        if thousand:\n",
    "            res.append(self.helper(thousand)+' Thousand')\n",
    "        if rest:\n",
    "            res.append(self.helper(rest))\n",
    "        return ' '.join(res)\n",
    "\n",
    "        \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "singles = [\"\", \"One\", \"Two\", \"Three\", \"Four\", \"Five\", \"Six\", \"Seven\", \"Eight\", \"Nine\"]\n",
    "teens = [\"Ten\", \"Eleven\", \"Twelve\", \"Thirteen\", \"Fourteen\", \"Fifteen\", \"Sixteen\", \"Seventeen\", \"Eighteen\", \"Nineteen\"]\n",
    "tens = [\"\", \"Ten\", \"Twenty\", \"Thirty\", \"Forty\", \"Fifty\", \"Sixty\", \"Seventy\", \"Eighty\", \"Ninety\"]\n",
    "thousands = [\"\", \"Thousand\", \"Million\", \"Billion\"]\n",
    "\n",
    "class Solution:\n",
    "    def numberToWords(self, num: int) -> str:\n",
    "        ans=''\n",
    "        x=1000000000\n",
    "        i=3\n",
    "        if num==0:\n",
    "            return 'Zero'\n",
    "        while x>0:\n",
    "            y=num//x\n",
    "            h,t,s=y//100,(y%100//10),y%10\n",
    "            if h>0:\n",
    "                ans+=singles[h]+' Hundred '\n",
    "            if t>1:\n",
    "                ans+=tens[t]+' '\n",
    "            if t==1:\n",
    "                ans+=teens[s]+' '\n",
    "            elif s>0:\n",
    "                ans+=singles[s]+' '\n",
    "            if y>0:\n",
    "                ans+=thousands[i]+' '\n",
    "            num=num%x\n",
    "            x//=1000\n",
    "            i-=1\n",
    "        # return ans[:-1 if ans[-2]!=' ' else -2]\n",
    "        return ans.strip()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numberToWords(self, num: int) -> str:\n",
    "        def f(temp):\n",
    "            ss = ''\n",
    "            if temp == 0: return ss\n",
    "            elif temp < 10: \n",
    "                ss += singles[temp] + ' '\n",
    "            elif temp < 20:\n",
    "                ss += teens[temp - 10] + ' '\n",
    "            elif temp < 100:\n",
    "                ss += tens[temp//10] + ' ' + f(temp%10)\n",
    "            else:\n",
    "                ss += singles[temp//100] + ' ' + 'Hundred' + ' ' + f(temp%100)\n",
    "            return ss\n",
    "        \n",
    "        singles = [\"\", \"One\", \"Two\", \"Three\", \"Four\", \"Five\", \"Six\", \"Seven\", \"Eight\", \"Nine\"]\n",
    "        teens = [\"Ten\", \"Eleven\", \"Twelve\", \"Thirteen\", \"Fourteen\", \"Fifteen\", \"Sixteen\", \"Seventeen\", \"Eighteen\", \"Nineteen\"]\n",
    "        tens = [\"\", \"Ten\", \"Twenty\", \"Thirty\", \"Forty\", \"Fifty\", \"Sixty\", \"Seventy\", \"Eighty\", \"Ninety\"]\n",
    "        thousands = [\"\", \"Thousand \", \"Million \", \"Billion \"]\n",
    "        \n",
    "        if num == 0: return 'Zero'\n",
    "        k = 0\n",
    "        s = ''\n",
    "        while num > 0:\n",
    "            temp = num % 1000\n",
    "            if f(temp) != '':\n",
    "                s = f(temp) + thousands[k] + s \n",
    "            num //= 1000\n",
    "            k += 1\n",
    "        return s.strip()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "singles = [\"\", \"One\", \"Two\", \"Three\", \"Four\", \"Five\", \"Six\", \"Seven\", \"Eight\", \"Nine\"]\n",
    "teens = [\"Ten\", \"Eleven\", \"Twelve\", \"Thirteen\", \"Fourteen\", \"Fifteen\", \"Sixteen\", \"Seventeen\", \"Eighteen\", \"Nineteen\"]\n",
    "tens = [\"\", \"Ten\", \"Twenty\", \"Thirty\", \"Forty\", \"Fifty\", \"Sixty\", \"Seventy\", \"Eighty\", \"Ninety\"]\n",
    "thousands = [\"\", \"Thousand\", \"Million\", \"Billion\"]\n",
    "\n",
    "class Solution:\n",
    "    def numberToWords(self, num: int) -> str:\n",
    "        if num == 0:\n",
    "            return \"Zero\"\n",
    "\n",
    "        def recursion(num: int) -> str:\n",
    "            s = \"\"\n",
    "            if num == 0:\n",
    "                return s\n",
    "            elif num < 10:\n",
    "                s += singles[num] + \" \"\n",
    "            elif num < 20:\n",
    "                s += teens[num - 10] + \" \"\n",
    "            elif num < 100:\n",
    "                s += tens[num // 10] + \" \" + recursion(num % 10)\n",
    "            else:\n",
    "                s += singles[num // 100] + \" Hundred \" + recursion(num % 100)\n",
    "            return s\n",
    "\n",
    "        s = \"\"\n",
    "        unit = int(1e9)\n",
    "        for i in range(3, -1, -1):\n",
    "            curNum = num // unit\n",
    "            if curNum:\n",
    "                num -= curNum * unit\n",
    "                s += recursion(curNum) + thousands[i] + \" \"\n",
    "            unit //= 1000\n",
    "        return s.strip()\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numberToWords(self, num: int) -> str:\n",
    "        match = {0: 'Zero', 1: 'One', 2: 'Two', 3: 'Three', 4: 'Four', 5: 'Five', 6: 'Six', 7: 'Seven', 8: 'Eight', 9: 'Nine', 10: 'Ten',\n",
    "        11: 'Eleven', 12: 'Twelve', 13: 'Thirteen', 14: 'Fourteen', 15: 'Fifteen', 16: 'Sixteen', 17: 'Seventeen', 18: 'Eighteen',\n",
    "        19: 'Nineteen', 20: 'Twenty', 30: 'Thirty', 40: 'Forty', 50: 'Fifty', 60: 'Sixty', 70: 'Seventy', 80: 'Eighty', 90: 'Ninety'}\n",
    "        if num <= 20 or (num < 100 and num % 10 == 0):\n",
    "            return match[num]\n",
    "\n",
    "        def getRight(n: int) -> str:\n",
    "            R = n % 100\n",
    "            L = (n - R) // 100\n",
    "            # print(R, L)\n",
    "            res = \"\"\n",
    "            if L != 0:\n",
    "                # print(match[L])\n",
    "                res += match[L] + \" \" + \"Hundred \"\n",
    "            if R <= 20 or (R < 100 and R % 10 == 0):\n",
    "                res += match[R] + \" \" if R != 0 else \"\"\n",
    "            else:\n",
    "                p = R % 10\n",
    "                n = R - p\n",
    "                res += match[n] + \" \" + match[p] + \" \" if n != 0 else match[p] + \" \"\n",
    "            return res\n",
    "        def getLeft(n: int) -> str:\n",
    "            if n <= 20 or (n < 100 and n % 10 == 0):\n",
    "                return match[num] + \" \" if n != 0 else \"\"\n",
    "            p = n % 10\n",
    "            n = n - p\n",
    "            return match[n] + \" \" + match[p] + \" \" if n != 0 else match[p] + \" \"\n",
    "\n",
    "        ans = getRight(num % 1000)\n",
    "        num = num // 1000\n",
    "        if num == 0:\n",
    "            return ans[:-1]\n",
    "        curr = getRight(num % 1000)\n",
    "        ans = curr + \"Thousand \" + ans if curr != \"\" else ans\n",
    "        num = num // 1000\n",
    "        if num == 0:\n",
    "            return ans[:-1]\n",
    "        curr = getRight(num % 1000)\n",
    "        ans = curr + \"Million \" + ans if curr != \"\" else ans\n",
    "        num = num // 1000\n",
    "        if num == 0:\n",
    "            return ans[:-1]\n",
    "        ans = getLeft(num) + \"Billion \" + ans\n",
    "        return ans[:-1]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "singles = [\"\", \"One\", \"Two\", \"Three\", \"Four\", \"Five\", \"Six\", \"Seven\", \"Eight\", \"Nine\"]\n",
    "teens = [\"Ten\", \"Eleven\", \"Twelve\", \"Thirteen\", \"Fourteen\", \"Fifteen\", \"Sixteen\", \"Seventeen\", \"Eighteen\", \"Nineteen\"]\n",
    "tens = [\"\", \"Ten\", \"Twenty\", \"Thirty\", \"Forty\", \"Fifty\", \"Sixty\", \"Seventy\", \"Eighty\", \"Ninety\"]\n",
    "thousands = [\"\", \"Thousand\", \"Million\", \"Billion\"]\n",
    "\n",
    "class Solution:\n",
    "    def numberToWords(self, num: int) -> str:\n",
    "        if num == 0:\n",
    "            return \"Zero\"\n",
    "\n",
    "        def toEnglish(num: int) -> str:\n",
    "            s = \"\"\n",
    "            if num >= 100:\n",
    "                s += singles[num // 100] + \" Hundred \"\n",
    "                num %= 100\n",
    "            if num >= 20:\n",
    "                s += tens[num // 10] + \" \"\n",
    "                num %= 10\n",
    "            if 0 < num < 10:\n",
    "                s += singles[num] + \" \"\n",
    "            elif num >= 10:\n",
    "                s += teens[num - 10] + \" \"\n",
    "            return s\n",
    "\n",
    "        s = \"\"\n",
    "        unit = int(1e9)\n",
    "        for i in range(3, -1, -1):\n",
    "            curNum = num // unit\n",
    "            if curNum:\n",
    "                num -= curNum * unit\n",
    "                s += toEnglish(curNum) + thousands[i] + \" \"\n",
    "            unit //= 1000\n",
    "        return s.strip()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numberToWords(self, num: int) -> str:\n",
    "        segment2Unit = [\n",
    "            '',\n",
    "            'Thousand',\n",
    "            'Million',\n",
    "            'Billion'\n",
    "        ]\n",
    "\n",
    "        def getCurWords(curNum):\n",
    "            digitMapping = [\n",
    "                '',\n",
    "                'One',\n",
    "                'Two',\n",
    "                'Three',\n",
    "                'Four',\n",
    "                'Five',\n",
    "                'Six',\n",
    "                'Seven',\n",
    "                'Eight',\n",
    "                'Nine',\n",
    "                'Ten',\n",
    "                'Eleven',\n",
    "                'Twelve',\n",
    "                'Thirteen',\n",
    "                'Fourteen',\n",
    "                'Fifteen',\n",
    "                'Sixteen',\n",
    "                'Seventeen',\n",
    "                'Eighteen',\n",
    "                'Nineteen'\n",
    "                ]\n",
    "            digitMapping2 = [\n",
    "                '',\n",
    "                'Ten',\n",
    "                'Twenty',\n",
    "                'Thirty',\n",
    "                'Forty',\n",
    "                'Fifty',\n",
    "                'Sixty',\n",
    "                'Seventy',\n",
    "                'Eighty',\n",
    "                'Ninety'\n",
    "                ]\n",
    "            results = []\n",
    "            if curNum >= 100:\n",
    "                hundredDigit = curNum // 100\n",
    "                results.append(digitMapping[hundredDigit])\n",
    "                results.append('Hundred')\n",
    "                curNum %= 100\n",
    "            \n",
    "            if curNum >= 20:\n",
    "                curDigit = curNum // 10\n",
    "                results.append(digitMapping2[curDigit])\n",
    "                curDigit = curNum % 10\n",
    "                if curDigit > 0:\n",
    "                    results.append(digitMapping[curDigit])\n",
    "            else: # 0 ~ 19\n",
    "                if curNum != 0:\n",
    "                    results.append(digitMapping[curNum])\n",
    "            \n",
    "            return results\n",
    "\n",
    "        curSegment = 0\n",
    "        results = []\n",
    "\n",
    "        while num:\n",
    "            curNum = num % 1000\n",
    "            if curNum != 0:\n",
    "                curResult = getCurWords(curNum)\n",
    "                if curSegment > 0:\n",
    "                    curResult.append(segment2Unit[curSegment])\n",
    "                results.append(' '.join(curResult))\n",
    "            num //= 1000\n",
    "            curSegment += 1\n",
    "        \n",
    "        results.reverse()\n",
    "        if len(results) == 0:\n",
    "            return 'Zero'\n",
    "        return ' '.join(results)\n",
    "        \n",
    "        \n",
    "        \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numberToWords(self, num: int) -> str:\n",
    "        digitMap = ['Zero', 'One', 'Two', 'Three', 'Four', 'Five', 'Six', 'Seven', 'Eight', 'Nine', 'Ten', 'Eleven', 'Twelve', 'Thirteen', 'Fourteen', 'Fifteen', 'Sixteen', 'Seventeen', 'Eighteen', 'Nineteen', 'Twenty']\n",
    "        decadeMap = {2: 'Twenty', 3: 'Thirty', 4: 'Forty', 5: 'Fifty', 6: 'Sixty', 7: 'Seventy', 8: 'Eighty', 9: 'Ninety'}\n",
    "        def toHundreds(n):\n",
    "            ws = []\n",
    "            h = n // 100\n",
    "            n %= 100\n",
    "            if h > 0:\n",
    "                ws.append(digitMap[h])\n",
    "                ws.append('Hundred')\n",
    "            if 0 < n <= 20:\n",
    "                ws.append(digitMap[n])\n",
    "            elif n > 20:\n",
    "                d = n // 10\n",
    "                ws.append(decadeMap[d])\n",
    "                if n % 10 != 0:\n",
    "                    ws.append(digitMap[n % 10])\n",
    "            return ws\n",
    "\n",
    "        if num == 0:\n",
    "            return digitMap[0]\n",
    "        mag = [1000000000, 1000000, 1000]\n",
    "        magMap = ['Billion', 'Million', 'Thousand']\n",
    "        words = []\n",
    "        for i, m in enumerate(mag):\n",
    "            h = num // m\n",
    "            num %= m\n",
    "            if h > 0:\n",
    "                words.extend(toHundreds(h))\n",
    "                words.append(magMap[i])\n",
    "        if num > 0:\n",
    "            words.extend(toHundreds(num))\n",
    "        \n",
    "        return ' '.join(words)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numberToWords(self, num: int) -> str:\n",
    "        if num == 0:\n",
    "            return 'Zero'\n",
    "        s = str(num)[::-1]\n",
    "        n = len(s)\n",
    "        #  || 9 8 7 || 6 5 4 || 3 2 1\n",
    "        kv_001 = {'1': 'One', '2': 'Two', '3': 'Three', '4': 'Four', '5': 'Five',\n",
    "                  '6': 'Six', '7': 'Seven', '8': 'Eight', '9': 'Nine'}\n",
    "        kv_001_ = {'1': 'Eleven', '2': 'Twelve', '3': 'Thirteen', '4': 'Fourteen', \n",
    "        '5': 'Fifteen', '6': 'Sixteen', '7': 'Seventeen', '8': 'Eighteen',\n",
    "        '9': 'Nineteen', '0': 'Ten'}\n",
    "        kv_010 = {'2': 'Twenty', '3': 'Thirty', '4': 'Forty', '5': 'Fifty', '6': 'Sixty',\n",
    "        '7': 'Seventy', '8': 'Eighty', '9': 'Ninety'}\n",
    "        def read(hundred, ten, one):\n",
    "            word = []\n",
    "            if hundred:\n",
    "                word.append(kv_001[hundred] + ' Hundred')\n",
    "            if ten == None:\n",
    "                if one == None:\n",
    "                    return ''\n",
    "                else:\n",
    "                    if one != '0':\n",
    "                        word.append(kv_001[one])\n",
    "            elif ten == '1':\n",
    "                word.append(kv_001_[one])\n",
    "            elif ten == '0':\n",
    "                if one and one != '0':\n",
    "                    word.append(kv_001[one])\n",
    "            else:\n",
    "                word.append(kv_010[ten])\n",
    "                if one != '0':\n",
    "                    word.append(kv_001[one])\n",
    "            return ' '.join(word)\n",
    "        res = []\n",
    "        if n > 9:\n",
    "            hundred = s[12-1] if n >= 12 else None\n",
    "            if hundred == '0': hundred = None\n",
    "            ten = s[11-1] if n >= 11 else None\n",
    "            if ten == '0' and hundred == '0': ten = None\n",
    "            one = s[10-1]\n",
    "            if one == '0' and ten == '0' and hundred == '0': one = None\n",
    "            read_result = read(hundred, ten, one)\n",
    "            if read_result:\n",
    "                res.append(read_result + ' Billion')\n",
    "        if n > 6:\n",
    "            hundred = s[9-1] if n >= 9 else None\n",
    "            if hundred == '0': hundred = None\n",
    "            ten = s[8-1] if n >= 8 else None\n",
    "            if ten == '0' and hundred == '0': ten = None\n",
    "            one = s[7-1]\n",
    "            if one == '0' and ten == '0' and hundred == '0': one = None\n",
    "            read_result = read(hundred, ten, one)\n",
    "            if read_result:\n",
    "                res.append(read_result + ' Million')\n",
    "        if n > 3:\n",
    "            hundred = s[6-1] if n >= 6 else None\n",
    "            if hundred == '0': hundred = None\n",
    "            ten = s[5-1] if n >= 5 else None\n",
    "            if ten == '0' and hundred == '0': ten = None\n",
    "            one = s[4-1]\n",
    "            if one == '0' and ten == '0' and hundred == '0': one = None\n",
    "            read_result = read(hundred, ten, one)\n",
    "            if read_result:\n",
    "                res.append(read_result + ' Thousand')\n",
    "        if n > 0:\n",
    "            hundred = s[3-1] if n >= 3 else None\n",
    "            if hundred == '0': hundred = None\n",
    "            ten = s[2-1] if n >= 2 else None\n",
    "            if ten == '0' and hundred == '0': ten = None\n",
    "            one = s[1-1]\n",
    "            if one == '0' and ten == '0' and hundred == '0': one = None\n",
    "            read_result = read(hundred, ten, one)\n",
    "            if read_result:\n",
    "                res.append(read_result)\n",
    "        return ' '.join(res)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numberToWords(self, num: int) -> str:\n",
    "        if num == 0:\n",
    "            return \"Zero\"\n",
    "\n",
    "        singles = [\"\", \"One\", \"Two\", \"Three\", \"Four\", \"Five\", \"Six\", \"Seven\", \"Eight\", \"Nine\"]\n",
    "        teens = [\"Ten\", \"Eleven\", \"Twelve\", \"Thirteen\", \"Fourteen\", \"Fifteen\", \"Sixteen\", \"Seventeen\", \"Eighteen\", \"Nineteen\"]\n",
    "        tens = [\"\", \"\", \"Twenty\", \"Thirty\", \"Forty\", \"Fifty\", \"Sixty\", \"Seventy\", \"Eighty\", \"Ninety\"]\n",
    "        thousands = [\"\", \"Thousand\", \"Million\", \"Billion\"]\n",
    "\n",
    "        ans = \"\"\n",
    "        mod = 10**9\n",
    "        i = 3\n",
    "        while num > 0:\n",
    "            group = num // mod\n",
    "            if group > 0:\n",
    "                s = \"\"\n",
    "                if group >= 100:\n",
    "                    s += singles[group // 100] + \" Hundred \"\n",
    "                    group %= 100\n",
    "                if group >= 20:\n",
    "                    s += tens[group // 10] + \" \"\n",
    "                    group %= 10\n",
    "                \n",
    "                if group >= 10: # [10, 20)\n",
    "                    s += teens[group % 10] + \" \"\n",
    "                elif group > 0:  # 特别注意，个位为0的情况直接跳过\n",
    "                    s += singles[group] + \" \"\n",
    "                \n",
    "                s += thousands[i] + \" \"\n",
    "                ans += s\n",
    "\n",
    "            num %= mod\n",
    "            i -= 1\n",
    "            mod //= 1000\n",
    "\n",
    "        return ans.strip()\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numberToWords(self, num: int) -> str:\n",
    "        if num == 0:\n",
    "            return \"Zero\"\n",
    "        map_basic = ['Zero', 'One', 'Two', 'Three', 'Four', 'Five', 'Six', 'Seven', 'Eight', 'Nine' , 'Ten',\n",
    "        'Eleven', 'Twelve', 'Thirteen', 'Fourteen', 'Fifteen', 'Sixteen', 'Seventeen', 'Eighteen', 'Nineteen']\n",
    "        map_ty = {\n",
    "            2 : 'Twenty',\n",
    "            3 : 'Thirty',\n",
    "            4 : 'Forty',\n",
    "            5 : 'Fifty',\n",
    "            6 : 'Sixty',\n",
    "            7 : 'Seventy',\n",
    "            8 : 'Eighty',\n",
    "            9 : 'Ninety'\n",
    "        }\n",
    "        map_big = {\n",
    "            # 100 : 'Hundred',\n",
    "            1000 : 'Thousand',\n",
    "            1000000: 'Million',\n",
    "            1000000000: 'Billion'\n",
    "        }\n",
    "        def tohundred(num):\n",
    "            ws = []\n",
    "            h = num // 100\n",
    "            num = num % 100\n",
    "            if h > 0:\n",
    "                ws.append(map_basic[h])\n",
    "                ws.append('Hundred')\n",
    "            \n",
    "            if num >= 20:\n",
    "                h = num // 10\n",
    "                ws.append(map_ty[h])\n",
    "                if num % 10 != 0:\n",
    "                    ws.append(map_basic[num % 10])\n",
    "            elif  0 < num < 20:\n",
    "                ws.append(map_basic[num])\n",
    "            \n",
    "            return ws\n",
    "            \n",
    "\n",
    "        def tran(num, mag):\n",
    "            ws = []\n",
    "            if mag < 1000:\n",
    "                ws.extend(tohundred(num))\n",
    "            else:\n",
    "                h = num // mag\n",
    "                if h > 0:\n",
    "                    ws.extend(tohundred(h))\n",
    "                    ws.append(map_big[mag])\n",
    "                \n",
    "                ws.extend(tran(num % mag, mag // 1000))  # extend 添加多个元素\n",
    "            \n",
    "            return ws\n",
    "        \n",
    "        return ' '.join(tran(num, 1000000000))\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "singles = [\"\", \"One\", \"Two\", \"Three\", \"Four\", \"Five\", \"Six\", \"Seven\", \"Eight\", \"Nine\"]\n",
    "teens = [\"Ten\", \"Eleven\", \"Twelve\", \"Thirteen\", \"Fourteen\", \"Fifteen\", \"Sixteen\", \"Seventeen\", \"Eighteen\", \"Nineteen\"]\n",
    "tens = [\"\", \"Ten\", \"Twenty\", \"Thirty\", \"Forty\", \"Fifty\", \"Sixty\", \"Seventy\", \"Eighty\", \"Ninety\"]\n",
    "thousands = [\"\", \"Thousand\", \"Million\", \"Billion\"]\n",
    "\n",
    "class Solution:\n",
    "    def numberToWords(self, num: int) -> str:\n",
    "        if num == 0:\n",
    "            return \"Zero\"\n",
    "\n",
    "        def recursion(num: int) -> str:\n",
    "            s = \"\"\n",
    "            if num == 0:\n",
    "                return s\n",
    "            elif num < 10:\n",
    "                s += singles[num] + \" \"\n",
    "            elif num < 20:\n",
    "                s += teens[num - 10] + \" \"\n",
    "            elif num < 100:\n",
    "                s += tens[num // 10] + \" \" + recursion(num % 10)\n",
    "            else:\n",
    "                s += singles[num // 100] + \" Hundred \" + recursion(num % 100)\n",
    "            return s\n",
    "\n",
    "        s = \"\"\n",
    "        unit = int(1e9)\n",
    "        for i in range(3, -1, -1):\n",
    "            curNum = num // unit\n",
    "            if curNum:\n",
    "                num -= curNum * unit\n",
    "                s += recursion(curNum) + thousands[i] + \" \"\n",
    "            unit //= 1000\n",
    "        return s.strip()\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numberToWords(self, num: int) -> str:\n",
    "        \n",
    "        singles = [\"\", \"One\", \"Two\", \"Three\", \"Four\", \"Five\", \"Six\", \"Seven\", \"Eight\", \"Nine\"]\n",
    "        teens = [\"Ten\", \"Eleven\", \"Twelve\", \"Thirteen\", \"Fourteen\", \"Fifteen\", \"Sixteen\", \"Seventeen\", \"Eighteen\", \"Nineteen\"]\n",
    "        \n",
    "        tens = [\"\", \"Ten\", \"Twenty\", \"Thirty\", \"Forty\", \"Fifty\", \"Sixty\", \"Seventy\", \"Eighty\", \"Ninety\"]\n",
    "        thousands = [\"\", \"Thousand\", \"Million\", \"Billion\"]\n",
    "        \"\"\"\n",
    "        if num == 0:\n",
    "            return \"Zero\"\n",
    "\n",
    "        def recursion(num: int) -> str:\n",
    "            s = \"\"\n",
    "            if num == 0:\n",
    "                return s\n",
    "            elif num < 10:\n",
    "                s += singles[num] + \" \"\n",
    "            elif num < 20:\n",
    "                s += teens[num - 10] + \" \"\n",
    "            elif num < 100:\n",
    "                s += tens[num // 10] + \" \" + recursion(num % 10)\n",
    "            else:\n",
    "                s += singles[num // 100] + \" Hundred \" + recursion(num % 100)\n",
    "            return s\n",
    "\n",
    "        s = \"\"\n",
    "        unit = int(1e9)\n",
    "\n",
    "        for i in range(3, -1, -1):\n",
    "            curNum = num // unit\n",
    "            print(curNum)\n",
    "            if curNum:\n",
    "                num -= curNum * unit\n",
    "                print(num)\n",
    "                s += recursion(curNum) + thousands[i] + \" \"\n",
    "            unit //= 1000\n",
    "        return s.strip()\n",
    "        \"\"\"\n",
    "        if num == 0:\n",
    "            return \"Zero\"\n",
    "\n",
    "        def toEnglish(num: int) -> str:\n",
    "            s = \"\"\n",
    "            if num >= 100:\n",
    "                s += singles[num // 100] + \" Hundred \"\n",
    "                num %= 100\n",
    "            if num >= 20:\n",
    "                s += tens[num // 10] + \" \"\n",
    "                num %= 10\n",
    "            if 0 < num < 10:\n",
    "                s += singles[num] + \" \"\n",
    "            elif num >= 10:\n",
    "                s += teens[num - 10] + \" \"\n",
    "            return s\n",
    "\n",
    "        s = \"\"\n",
    "        unit = int(1e9)\n",
    "        for i in range(3, -1, -1):\n",
    "            curNum = num // unit\n",
    "            if curNum:\n",
    "                num -= curNum * unit\n",
    "                s += toEnglish(curNum) + thousands[i] + \" \"\n",
    "            unit //= 1000\n",
    "        return s.strip()\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numberToWords(self, num: int) -> str:\n",
    "        match = {0: 'Zero', 1: 'One', 2: 'Two', 3: 'Three', 4: 'Four', 5: 'Five', 6: 'Six', 7: 'Seven', 8: 'Eight', 9: 'Nine', 10: 'Ten',\n",
    "        11: 'Eleven', 12: 'Twelve', 13: 'Thirteen', 14: 'Fourteen', 15: 'Fifteen', 16: 'Sixteen', 17: 'Seventeen', 18: 'Eighteen',\n",
    "        19: 'Nineteen', 20: 'Twenty', 30: 'Thirty', 40: 'Forty', 50: 'Fifty', 60: 'Sixty', 70: 'Seventy', 80: 'Eighty', 90: 'Ninety'}\n",
    "        if num <= 20 or (num < 100 and num % 10 == 0):\n",
    "            return match[num]\n",
    "\n",
    "        def getRight(n: int) -> str:\n",
    "            R = n % 100\n",
    "            L = (n - R) // 100\n",
    "            res = \"\"\n",
    "            if L != 0:\n",
    "                res += match[L] + \" \" + \"Hundred \"\n",
    "            if R <= 20 or (R < 100 and R % 10 == 0):\n",
    "                res += match[R] + \" \" if R != 0 else \"\"\n",
    "            else:\n",
    "                p = R % 10\n",
    "                n = R - p\n",
    "                res += match[n] + \" \" + match[p] + \" \" if n != 0 else match[p] + \" \"\n",
    "            return res\n",
    "        def getLeft(n: int) -> str:\n",
    "            if n <= 20 or (n < 100 and n % 10 == 0):\n",
    "                return match[num] + \" \" if n != 0 else \"\"\n",
    "            p = n % 10\n",
    "            n = n - p\n",
    "            return match[n] + \" \" + match[p] + \" \" if n != 0 else match[p] + \" \"\n",
    "\n",
    "        ans = getRight(num % 1000)\n",
    "        num = num // 1000\n",
    "        if num == 0:\n",
    "            return ans[:-1]\n",
    "        curr = getRight(num % 1000)\n",
    "        ans = curr + \"Thousand \" + ans if curr != \"\" else ans\n",
    "        num = num // 1000\n",
    "        if num == 0:\n",
    "            return ans[:-1]\n",
    "        curr = getRight(num % 1000)\n",
    "        ans = curr + \"Million \" + ans if curr != \"\" else ans\n",
    "        num = num // 1000\n",
    "        if num == 0:\n",
    "            return ans[:-1]\n",
    "        ans = getLeft(num) + \"Billion \" + ans\n",
    "        return ans[:-1]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numberToWords(self, num: int) -> str:\n",
    "        mapping = {\n",
    "          1000000000: 'Billion',\n",
    "          1000000: 'Million',\n",
    "          1000: 'Thousand',\n",
    "          100: 'Hundred',\n",
    "          90: 'Ninety',\n",
    "          80: 'Eighty',\n",
    "          70: 'Seventy',\n",
    "          60: 'Sixty',\n",
    "          50: 'Fifty',\n",
    "          40: 'Forty',\n",
    "          30: 'Thirty',\n",
    "          20: 'Twenty',\n",
    "          19: 'Nineteen',\n",
    "          18: 'Eighteen',\n",
    "          17: 'Seventeen',\n",
    "          16: 'Sixteen',\n",
    "          15: 'Fifteen',\n",
    "          14: 'Fourteen',\n",
    "          13: 'Thirteen',\n",
    "          12: 'Twelve',\n",
    "          11: 'Eleven',\n",
    "          10: 'Ten',\n",
    "          9: 'Nine',\n",
    "          8: 'Eight',\n",
    "          7: 'Seven',\n",
    "          6: 'Six',\n",
    "          5: 'Five',\n",
    "          4: 'Four',\n",
    "          3: 'Three',\n",
    "          2: 'Two',\n",
    "          1: 'One'\n",
    "        }\n",
    "        if num==0:\n",
    "            return \"Zero\"\n",
    "        result=\"\"\n",
    "        \n",
    "        for value, name in mapping.items():\n",
    "            count=0\n",
    "            if num>=value:\n",
    "               count=num//value\n",
    "               num%=value\n",
    "               if count>1 or value>=100:\n",
    "                   result= result+\" \"+self.numberToWords(count)+\" \"+name\n",
    "               else:\n",
    "                   result+=\" \"+name\n",
    "        result=result[1:]\n",
    "        return result"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numberToWords(self, num: int) -> str:\n",
    "        ones = [\"One\", \"Two\", \"Three\", \"Four\", \"Five\", \"Six\", \"Seven\", \"Eight\", \"Nine\"]\n",
    "        teens = [\"Ten\", \"Eleven\", \"Twelve\", \"Thirteen\", \"Fourteen\", \"Fifteen\", \"Sixteen\", \"Seventeen\", \"Eighteen\", \"Nineteen\"]\n",
    "        tens = [\"Twenty\", \"Thirty\", \"Forty\", \"Fifty\", \"Sixty\", \"Seventy\", \"Eighty\", \"Ninety\"]\n",
    "        eles = [\"Billion\", \"Million\", \"Thousand\", \"\"]\n",
    "        \n",
    "        def dfs(n):\n",
    "            if n == 0:\n",
    "                return \"\"\n",
    "            elif n < 10:\n",
    "                return ones[n - 1] + \" \"\n",
    "            elif n < 20:\n",
    "                return teens[n % 10] + \" \"\n",
    "            elif n < 100:\n",
    "                return tens[n // 10 - 2] + \" \" + dfs(n % 10)\n",
    "            else:\n",
    "                return ones[n // 100 - 1] + \" Hundred \" + dfs(n % 100)\n",
    "        \n",
    "        mul = 10 ** 9\n",
    "        ans = \"\"\n",
    "\n",
    "        for i in range(4):\n",
    "            if num // mul:\n",
    "                ans += dfs(num // mul)\n",
    "                ans += eles[i] + \" \"\n",
    "            num %= mul\n",
    "            mul //= (10 ** 3)\n",
    "        \n",
    "        return ans.strip() if ans else \"Zero\"\n",
    "                "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numberToWords(self, num: int) -> str:\n",
    "        numToStr = { 1:'One', 2:'Two', 3:'Three', 4:'Four', 5:'Five', 6:'Six', 7:'Seven', 8:'Eight', 9:'Nine', 10: 'Ten', 11: 'Eleven', 12: 'Twelve', 13:'Thirteen', 14:'Fourteen', 15:'Fifteen', 16:'Sixteen', 17:'Seventeen', 18:'Eighteen', 19:'Nineteen', 20: 'Twenty', 30:'Thirty', 40:'Forty', 50:'Fifty', 60:'Sixty', 70:'Seventy', 80:'Eighty', 90:'Ninety', 100:\"Hundred\"}\n",
    "        if num == 0: return 'Zero'\n",
    "\n",
    "        def getTenth(n):\n",
    "            if n == 0:return \"\"\n",
    "            if n%10 == 0 or n < 20: return f' {numToStr[n]}'\n",
    "            return f' {numToStr[(n//10)*10]} {numToStr[n%10]}'\n",
    "\n",
    "        def getHundreds(n):\n",
    "            if n//100 == 0: return getTenth(n)\n",
    "            return f' {numToStr[n//100]} Hundred'+getTenth(n%100)\n",
    "        \n",
    "        def getThousands(n):\n",
    "            if n//1000==0: return getHundreds(n)\n",
    "            return f' {ripLeadingSpace(getHundreds(n//1000))} Thousand'+getHundreds(n%1000)\n",
    "        \n",
    "        def getMillions(n):\n",
    "            if n//1000000==0: return getThousands(n)\n",
    "            return f' {ripLeadingSpace(getThousands(n//1000000))} Million'+getThousands(n%1000000)\n",
    "\n",
    "        def getBillions(n):\n",
    "            if n//1000000000==0:return getMillions(n)\n",
    "            return f' {ripLeadingSpace(getThousands(n//1000000000))} Billion'+getMillions(n%1000000000)        \n",
    "        def ripLeadingSpace(s):\n",
    "            if s and s[0] == ' ':\n",
    "                return s[1:]\n",
    "            return s\n",
    "\n",
    "\n",
    "        return ripLeadingSpace(getBillions(num))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "WORDS = [\n",
    "    None, \n",
    "    \"One\",\n",
    "    \"Two\",\n",
    "    \"Three\",\n",
    "    \"Four\",\n",
    "    \"Five\",\n",
    "    \"Six\",\n",
    "    \"Seven\",\n",
    "    \"Eight\",\n",
    "    \"Nine\",\n",
    "    \"Ten\",\n",
    "    \"Eleven\",\n",
    "    \"Twelve\",\n",
    "    \"Thirteen\",\n",
    "    \"Fourteen\",\n",
    "    \"Fifteen\",\n",
    "    \"Sixteen\",\n",
    "    \"Seventeen\",\n",
    "    \"Eighteen\",\n",
    "    \"Nineteen\",\n",
    "    \"Twenty\",\n",
    "    \"Thirty\",\n",
    "    \"Forty\",\n",
    "    \"Fifty\",\n",
    "    \"Sixty\",\n",
    "    \"Seventy\",\n",
    "    \"Eighty\",\n",
    "    \"Ninety\"\n",
    "]\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def process_3_group(self, a, b, c, postfix):\n",
    "        words = []\n",
    "        if a != 0:\n",
    "            words.append(WORDS[a])\n",
    "            words.append(\"Hundred\")\n",
    "        if b >= 2:\n",
    "            words.append(WORDS[b + 18])\n",
    "            if c != 0:\n",
    "                words.append(WORDS[c])\n",
    "        else:\n",
    "            to_append = WORDS[b * 10 + c]\n",
    "            if to_append is not None:\n",
    "                words.append(to_append)\n",
    "        if postfix is not None:\n",
    "            words.append(postfix)\n",
    "        return \" \".join(words)\n",
    "\n",
    "    def numberToWords(self, num: int) -> str:\n",
    "        if num == 0:\n",
    "            return \"Zero\"\n",
    "        words = []\n",
    "        postfixes = [None, \"Thousand\", \"Million\", \"Billion\"]\n",
    "        group = 0\n",
    "        while num != 0:\n",
    "            ns = [0, 0, 0]\n",
    "            i = 2\n",
    "            while num != 0 and i >= 0:\n",
    "                ns[i] = num % 10\n",
    "                num //= 10\n",
    "                i -= 1\n",
    "            if any(n != 0 for n in ns):\n",
    "                words.append(self.process_3_group(*ns, postfixes[group]))\n",
    "            group += 1\n",
    "        return \" \".join(reversed(words))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numberToWords(self, num: int) -> str:\n",
    "        if num == 0:\n",
    "            return 'Zero'\n",
    "        num_eng = {'0': '', '1': ' One', '2': ' Two', '3': ' Three', '4': ' Four', '5': ' Five', '6': ' Six', '7': ' Seven', '8': ' Eight', '9': ' Nine'}\n",
    "        num_eng_teen = {'0': ' Ten', '1': ' Eleven', '2': ' Twelve', '3': ' Thirteen', '4': ' Fourteen', '5': ' Fifteen', '6': ' Sixteen', '7': ' Seventeen', '8': ' Eighteen', '9': ' Nineteen'}\n",
    "        num_eng_ty = {'0': '', '2': ' Twenty', '3': ' Thirty', '4': ' Forty', '5': ' Fifty', '6': ' Sixty', '7': ' Seventy', '8': ' Eighty', '9': ' Ninety'}\n",
    "        digit = ['',' Thousand',' Million',' Billion']\n",
    "        num = str(num)\n",
    "        num_List = []\n",
    "        n = len(num)\n",
    "        i = n\n",
    "        while i > 3:\n",
    "            num_List.append(num[i - 3: i])\n",
    "            i -= 3\n",
    "        num_List.append(num[:i])\n",
    "        m = len(num_List)\n",
    "        ans = ''\n",
    "        for j in range(m):\n",
    "            if j == m - 1:\n",
    "                if len(num_List[j]) == 1:\n",
    "                    ans = num_eng[num_List[j]] + digit[j] + ans\n",
    "                    break\n",
    "                elif len(num_List[j]) == 2:\n",
    "                    if num_List[j][0] == '1':\n",
    "                        ans = num_eng_teen[num_List[j][1]] + digit[j] + ans\n",
    "                    else:\n",
    "                        ans = num_eng_ty[num_List[j][0]] + num_eng[num_List[j][1]] + digit[j] + ans\n",
    "                    break\n",
    "            if num_List[j] == '000':\n",
    "                continue\n",
    "            a = ''\n",
    "            if num_List[j][0] != '0':\n",
    "                a += num_eng[num_List[j][0]] + ' Hundred'\n",
    "            if num_List[j][1] == '1':\n",
    "                a += num_eng_teen[num_List[j][2]] + digit[j]\n",
    "            else:\n",
    "                a += num_eng_ty[num_List[j][1]] + num_eng[num_List[j][2]] + digit[j]\n",
    "            ans = a + ans\n",
    "        return ans[1:]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "singles = [\"\", \"One\", \"Two\", \"Three\", \"Four\", \"Five\", \"Six\", \"Seven\", \"Eight\", \"Nine\"]\n",
    "teens = [\"Ten\", \"Eleven\", \"Twelve\", \"Thirteen\", \"Fourteen\", \"Fifteen\", \"Sixteen\", \"Seventeen\", \"Eighteen\", \"Nineteen\"]\n",
    "tens = [\"\", \"Ten\", \"Twenty\", \"Thirty\", \"Forty\", \"Fifty\", \"Sixty\", \"Seventy\", \"Eighty\", \"Ninety\"]\n",
    "thousands = [\"\", \"Thousand\", \"Million\", \"Billion\"]\n",
    "\n",
    "class Solution:\n",
    "    def numberToWords(self, num: int) -> str:\n",
    "        if num == 0:\n",
    "            return \"Zero\"\n",
    "\n",
    "        def recursion(num: int) -> str:\n",
    "            s = \"\"\n",
    "            if num == 0:\n",
    "                return s\n",
    "            elif num < 10:\n",
    "                s += singles[num] + \" \"\n",
    "            elif num < 20:\n",
    "                s += teens[num - 10] + \" \"\n",
    "            elif num < 100:\n",
    "                s += tens[num // 10] + \" \" + recursion(num % 10)\n",
    "            else:\n",
    "                s += singles[num // 100] + \" Hundred \" + recursion(num % 100)\n",
    "            return s\n",
    "\n",
    "        s = \"\"\n",
    "        unit = int(1e9)\n",
    "        for i in range(3, -1, -1):\n",
    "            curNum = num // unit\n",
    "            if curNum:\n",
    "                num -= curNum * unit\n",
    "                s += recursion(curNum) + thousands[i] + \" \"\n",
    "            unit //= 1000\n",
    "        return s.strip()\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    b = \"Billion\"\n",
    "    m = \"Million\"\n",
    "    k = \"Thousand\"\n",
    "    h = \"Hundred\"\n",
    "    teens = {10:\"Ten\",11:\"Eleven\",12:\"Twelve\",13:\"Thirteen\",14:\"Fourteen\",\n",
    "        15:\"Fifteen\",16:\"Sixteen\",17:\"Seventeen\",18:\"Eighteen\",19:\"Nineteen\"}\n",
    "    tyies = {20:\"Twenty\",30:\"Thirty\",40:\"Forty\",50:\"Fifty\",60:\"Sixty\",70:\"Seventy\",\n",
    "        80:\"Eighty\",90:\"Ninety\"}\n",
    "    nums = {1:\"One\",2:\"Two\",3:\"Three\",4:\"Four\",5:\"Five\",6:\"Six\",7:\"Seven\",\n",
    "        8:\"Eight\",9:\"Nine\"}\n",
    "    def getNumberLess1h(self, a):\n",
    "        s = \"\"\n",
    "        if(a>=20):\n",
    "            print(a)\n",
    "            s += self.tyies[(int)(a/10)*10]\n",
    "            a = a%10\n",
    "            if(a>0):\n",
    "                s += \" \"+self.nums[a]\n",
    "        elif(a>=10):\n",
    "            s += self.teens[a]\n",
    "            a = 0\n",
    "        elif(a>0):\n",
    "            s += self.nums[a]\n",
    "        #print(\"<1h:\"+s)\n",
    "        return s\n",
    "    def getNumberLess1k(self, a):\n",
    "        s = \"\"\n",
    "        if(a>=100):\n",
    "            s += self.nums[(int)(a/100)]+\" \"+self.h\n",
    "            a = a%100\n",
    "            s1 = self.getNumberLess1h(a)\n",
    "            if(s1!=\"\"):\n",
    "                s += \" \"+s1\n",
    "        else:\n",
    "            s += self.getNumberLess1h(a)\n",
    "        #print(\"<1k:\"+s)\n",
    "        return s\n",
    "    def numberToWords(self, num: int) -> str:\n",
    "        if(num == 0):\n",
    "            return \"Zero\"\n",
    "        s = \"\"\n",
    "        bs = (int)(num/1000000000)\n",
    "        shouldHaveSpace = False\n",
    "        if(bs>0):\n",
    "            s += self.getNumberLess1k(bs)+\" \"+self.b\n",
    "            num = num%1000000000\n",
    "            shouldHaveSpace = True\n",
    "        ms = (int)(num/1000000)\n",
    "        if(ms>0):\n",
    "            if(shouldHaveSpace): s+=\" \"\n",
    "            s += self.getNumberLess1k(ms)+\" \"+self.m\n",
    "            num = num%1000000\n",
    "            shouldHaveSpace = True\n",
    "        ks = (int)(num/1000)\n",
    "        if(ks>0):\n",
    "            if(shouldHaveSpace): s+=\" \"\n",
    "            s += self.getNumberLess1k(ks)+\" \"+self.k\n",
    "            num = num%1000\n",
    "            shouldHaveSpace = True\n",
    "        s1 = self.getNumberLess1k(num)\n",
    "        if(s1!=\"\"):\n",
    "            if(shouldHaveSpace): s+=\" \"\n",
    "            s += s1\n",
    "        #print(s)\n",
    "        return s\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numberToWords(self, num: int) -> str:\n",
    "        match = {0: 'Zero', 1: 'One', 2: 'Two', 3: 'Three', 4: 'Four', 5: 'Five', 6: 'Six', 7: 'Seven', 8: 'Eight', 9: 'Nine', 10: 'Ten',\n",
    "        11: 'Eleven', 12: 'Twelve', 13: 'Thirteen', 14: 'Fourteen', 15: 'Fifteen', 16: 'Sixteen', 17: 'Seventeen', 18: 'Eighteen',\n",
    "        19: 'Nineteen', 20: 'Twenty', 30: 'Thirty', 40: 'Forty', 50: 'Fifty', 60: 'Sixty', 70: 'Seventy', 80: 'Eighty', 90: 'Ninety'}\n",
    "        if num <= 20 or (num < 100 and num % 10 == 0):\n",
    "            return match[num]\n",
    "\n",
    "        def getRight(n: int) -> str:\n",
    "            R = n % 100\n",
    "            L = (n - R) // 100\n",
    "            res = \"\"\n",
    "            if L != 0:\n",
    "                res += match[L] + \" \" + \"Hundred \"\n",
    "            if R <= 20 or (R < 100 and R % 10 == 0):\n",
    "                res += match[R] + \" \" if R != 0 else \"\"\n",
    "            else:\n",
    "                p = R % 10\n",
    "                n = R - p\n",
    "                res += match[n] + \" \" + match[p] + \" \" if n != 0 else match[p] + \" \"\n",
    "            return res\n",
    "        def getLeft(n: int) -> str:\n",
    "            if n <= 20 or (n < 100 and n % 10 == 0):\n",
    "                return match[num] + \" \" if n != 0 else \"\"\n",
    "            p = n % 10\n",
    "            n = n - p\n",
    "            return match[n] + \" \" + match[p] + \" \" if n != 0 else match[p] + \" \"\n",
    "\n",
    "        ans = getRight(num % 1000)\n",
    "        num = num // 1000\n",
    "        if num == 0:\n",
    "            return ans[:-1]\n",
    "        curr = getRight(num % 1000)\n",
    "        ans = curr + \"Thousand \" + ans if curr != \"\" else ans\n",
    "        num = num // 1000\n",
    "        if num == 0:\n",
    "            return ans[:-1]\n",
    "        curr = getRight(num % 1000)\n",
    "        ans = curr + \"Million \" + ans if curr != \"\" else ans\n",
    "        num = num // 1000\n",
    "        if num == 0:\n",
    "            return ans[:-1]\n",
    "        ans = getLeft(num) + \"Billion \" + ans\n",
    "        return ans[:-1]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numberToWords(self, num: int) -> str:\n",
    "\n",
    "\n",
    "        # 三个一组 每组单位\n",
    "        if num == 0: return \"Zero\"\n",
    "        singles = [\"\", \"One\", \"Two\", \"Three\", \"Four\", \"Five\", \"Six\", \"Seven\", \"Eight\", \"Nine\"]\n",
    "        teens = [\"Ten\", \"Eleven\", \"Twelve\", \"Thirteen\", \"Fourteen\", \"Fifteen\", \"Sixteen\", \"Seventeen\", \"Eighteen\", \"Nineteen\"]\n",
    "        tens = [\"\", \"Ten\", \"Twenty\", \"Thirty\", \"Forty\", \"Fifty\", \"Sixty\", \"Seventy\", \"Eighty\", \"Ninety\"]\n",
    "        thousands = [\"\", \"Thousand\", \"Million\", \"Billion\"]\n",
    "        # 递归\n",
    "        def num2str(num_):\n",
    "            s = \"\"\n",
    "            if num_ == 0:\n",
    "                return s\n",
    "            if 0< num_ < 10:\n",
    "                return  s + singles[num_] + \" \"\n",
    "            if 10<= num_ < 20:\n",
    "                return s + teens[num_%10] + \" \"\n",
    "            if 20<= num_ < 100:\n",
    "                return s + tens[num_//10] + \" \" + num2str(num_ % 10)\n",
    "            if 100<= num_:\n",
    "                return s + singles[num_//100] + \" Hundred \" + num2str(num_ % 100) \n",
    "        results = \"\"\n",
    "        unit = int(1e9)\n",
    "        # n = len(groups)\n",
    "        for i in range(3, -1, -1):\n",
    "            cur = num // unit\n",
    "            if cur:\n",
    "                results += num2str(cur) + thousands[i] + \" \"\n",
    "                num -= cur * unit\n",
    "            unit //= 1000\n",
    "\n",
    "        return results.strip()\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numberToWords(self, num: int) -> str:\n",
    "        ones = [\"One\", \"Two\", \"Three\", \"Four\", \"Five\", \"Six\", \"Seven\", \"Eight\", \"Nine\"]\n",
    "        teens = [\"Ten\", \"Eleven\", \"Twelve\", \"Thirteen\", \"Fourteen\", \"Fifteen\", \"Sixteen\", \"Seventeen\", \"Eighteen\", \"Nineteen\"]\n",
    "        tens = [\"Twenty\", \"Thirty\", \"Forty\", \"Fifty\", \"Sixty\", \"Seventy\", \"Eighty\", \"Ninety\"]\n",
    "        eles = [\"Billion\", \"Million\", \"Thousand\", \"\"]\n",
    "        \n",
    "        def dfs(n):\n",
    "            if n == 0:\n",
    "                return \"\"\n",
    "            elif n < 10:\n",
    "                return ones[n - 1] + \" \"\n",
    "            elif n < 20:\n",
    "                return teens[n - 10] + \" \"\n",
    "            elif n < 100:\n",
    "                return tens[n // 10 - 2] + \" \" + dfs(n % 10)\n",
    "            else:\n",
    "                return ones[n // 100 - 1] + \" Hundred \" + dfs(n % 100)\n",
    "            \n",
    "        mul = 10 ** 9\n",
    "        ans = \"\"\n",
    "        for i in range(4):\n",
    "            if num // mul:\n",
    "                ans += dfs(num // mul)\n",
    "                ans += eles[i]\n",
    "                ans += \" \"\n",
    "            num %= mul\n",
    "            mul //= 10 ** 3\n",
    "        \n",
    "        return ans.strip() if ans else \"Zero\""
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numberToWords(self, num: int) -> str:\n",
    "        basics=['','One','Two','Three','Four','Five','Six','Seven','Eight','Nine','Ten','Eleven','Twelve','Thirteen','Fourteen','Fifteen','Sixteen','Seventeen','Eighteen','Nineteen']\n",
    "        tens=['0','0','Twenty','Thirty','Forty','Fifty','Sixty','Seventy','Eighty','Ninety']\n",
    "        if num==0:\n",
    "            return 'Zero'\n",
    "        def find(nums):\n",
    "            if nums < 20:\n",
    "                return basics[nums]\n",
    "            elif nums < 100:\n",
    "                a,b = nums//10,nums%10\n",
    "                return tens[a]+' '+basics[b] if b !=0 else tens[a]\n",
    "            elif nums < 1000:\n",
    "                a,b = nums//100,nums%100\n",
    "                return basics[a] +' '+ 'Hundred' +' '+ find(b) if b !=0 else basics[a] +' '+ 'Hundred'\n",
    "            elif nums < 1000000:\n",
    "                a,b = nums//1000,nums%1000\n",
    "                return find(a) +' '+ 'Thousand' +' '+ find(b) if b !=0 else find(a) +' '+ 'Thousand'\n",
    "            elif nums < 1000000000:\n",
    "                a,b = nums//1000000,nums%1000000\n",
    "                return find(a)+ ' '+ 'Million' +' ' +find(b) if b !=0 else find(a) +' '+ 'Million'\n",
    "            elif nums < 1000000000000:\n",
    "                a,b = nums//1000000000,nums%1000000000\n",
    "                return find(a)+' ' + 'Billion' +' '+ find(b) if b !=0 else find(a) +' '+ 'Billion'\n",
    "        return find(num)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "singles = [\"\", \"One\", \"Two\", \"Three\", \"Four\", \"Five\", \"Six\", \"Seven\", \"Eight\", \"Nine\"]\n",
    "teens = [\"Ten\", \"Eleven\", \"Twelve\", \"Thirteen\", \"Fourteen\", \"Fifteen\", \"Sixteen\", \"Seventeen\", \"Eighteen\", \"Nineteen\"]\n",
    "tens = [\"\", \"Ten\", \"Twenty\", \"Thirty\", \"Forty\", \"Fifty\", \"Sixty\", \"Seventy\", \"Eighty\", \"Ninety\"]\n",
    "thousands = [\"\", \"Thousand\", \"Million\", \"Billion\"]\n",
    "\n",
    "class Solution:\n",
    "    def numberToWords(self, num: int) -> str:\n",
    "        if num == 0:\n",
    "            return \"Zero\"\n",
    "\n",
    "        def recursion(num: int) -> str:\n",
    "            s = \"\"\n",
    "            if num == 0:\n",
    "                return s\n",
    "            elif num < 10:\n",
    "                s += singles[num] + \" \"\n",
    "            elif num < 20:\n",
    "                s += teens[num - 10] + \" \"\n",
    "            elif num < 100:\n",
    "                s += tens[num // 10] + \" \" + recursion(num % 10)\n",
    "            else:\n",
    "                s += singles[num // 100] + \" Hundred \" + recursion(num % 100)\n",
    "            return s\n",
    "\n",
    "        s = \"\"\n",
    "        unit = int(1e9)\n",
    "        for i in range(3, -1, -1):\n",
    "            curNum = num // unit\n",
    "            if curNum:\n",
    "                num -= curNum * unit\n",
    "                s += recursion(curNum) + thousands[i] + \" \"\n",
    "            unit //= 1000\n",
    "        return s.strip()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numberToWords(self, num: int) -> str:\n",
    "      self.dic={'1':'One','2':'Two','3':'Three','4':'Four','5':'Five','6':'Six','7':'Seven','8':'Eight','9':'Nine','10':'Ten','11':'Eleven','12':'Twelve','13':'Thirteen','14':'Fourteen','15':'Fifteen','16':'Sixteen','17':'Seventeen','18':'Eighteen','19':'Nineteen','20':'Twenty','30':'Thirty','40':'Forty','50':'Fifty','60':'Sixty','70':'Seventy','80':'Eighty','90':'Ninety'}\n",
    "      temp=['',' Thousand',' Million',' Billion',' Thousand Billion']\n",
    "      num=str(num)\n",
    "      if num=='0':\n",
    "        return 'Zero'\n",
    "      ans=''\n",
    "      for i in range(0,len(num),3):\n",
    "        t=self.express(num[max(0,len(num)-(i+3)):len(num)-i],temp[i//3])\n",
    "        if t:\n",
    "          ans=t+' '+ans \n",
    "      return ans.rstrip()\n",
    "\n",
    "    def express(self,string,pos):\n",
    "      def get_expression(s):\n",
    "        if s=='00':\n",
    "          return ''\n",
    "        if s[0]=='0':\n",
    "          return self.dic[s[-1]]\n",
    "        if s in self.dic.keys():\n",
    "          return self.dic[s]\n",
    "        else:\n",
    "          return self.dic[s[0]+'0']+' '+self.dic[s[1]]\n",
    "      string=str(int(string))\n",
    "      if len(string)==0:\n",
    "        return ''\n",
    "      if int(string)==0:\n",
    "        return ''\n",
    "      elif len(string)==1:\n",
    "        return self.dic[string]+pos\n",
    "      elif len(string)==2:\n",
    "        return get_expression(string)+pos\n",
    "      else:\n",
    "        if string[1:]=='00':\n",
    "          return self.dic[string[0]]+' Hundred'+pos\n",
    "        else:\n",
    "          return self.dic[string[0]]+' Hundred '+get_expression(string[1:])+pos\n",
    "\n",
    "        \n",
    "      "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "singles = [\"\", \"One\", \"Two\", \"Three\", \"Four\", \"Five\", \"Six\", \"Seven\", \"Eight\", \"Nine\"]\n",
    "teens = [\"Ten\", \"Eleven\", \"Twelve\", \"Thirteen\", \"Fourteen\", \"Fifteen\", \"Sixteen\", \"Seventeen\", \"Eighteen\", \"Nineteen\"]\n",
    "tens = [\"\", \"Ten\", \"Twenty\", \"Thirty\", \"Forty\", \"Fifty\", \"Sixty\", \"Seventy\", \"Eighty\", \"Ninety\"]\n",
    "thousands = [\"\", \"Thousand\", \"Million\", \"Billion\"]\n",
    "\n",
    "class Solution:\n",
    "    def numberToWords(self, num: int) -> str:\n",
    "        if num == 0:\n",
    "            return \"Zero\"\n",
    "\n",
    "        def recursion(num: int) -> str:\n",
    "            s = \"\"\n",
    "            if num == 0:\n",
    "                return s\n",
    "            elif num < 10:\n",
    "                s += singles[num] + \" \"\n",
    "            elif num < 20:\n",
    "                s += teens[num - 10] + \" \"\n",
    "            elif num < 100:\n",
    "                s += tens[num // 10] + \" \" + recursion(num % 10)\n",
    "            else:\n",
    "                s += singles[num // 100] + \" Hundred \" + recursion(num % 100)\n",
    "            return s\n",
    "\n",
    "        s = \"\"\n",
    "        unit = int(1e9)\n",
    "        for i in range(3, -1, -1):\n",
    "            curNum = num // unit\n",
    "            if curNum:\n",
    "                num -= curNum * unit\n",
    "                s += recursion(curNum) + thousands[i] + \" \"\n",
    "            unit //= 1000\n",
    "        return s.strip()\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "singles = [\"\", \"One\", \"Two\", \"Three\", \"Four\", \"Five\", \"Six\", \"Seven\", \"Eight\", \"Nine\"]\n",
    "teens = [\"Ten\", \"Eleven\", \"Twelve\", \"Thirteen\", \"Fourteen\", \"Fifteen\", \"Sixteen\", \"Seventeen\", \"Eighteen\", \"Nineteen\"]\n",
    "tens = [\"\", \"Ten\", \"Twenty\", \"Thirty\", \"Forty\", \"Fifty\", \"Sixty\", \"Seventy\", \"Eighty\", \"Ninety\"]\n",
    "thousands = [\"\", \"Thousand\", \"Million\", \"Billion\"]\n",
    "\n",
    "class Solution:\n",
    "    def numberToWords(self, num: int) -> str:\n",
    "        if num == 0:\n",
    "            return \"Zero\"\n",
    "\n",
    "        def recursion(num: int) -> str:\n",
    "            s = \"\"\n",
    "            if num == 0:\n",
    "                return s\n",
    "            elif num < 10:\n",
    "                s += singles[num] + \" \"\n",
    "            elif num < 20:\n",
    "                s += teens[num - 10] + \" \"\n",
    "            elif num < 100:\n",
    "                s += tens[num // 10] + \" \" + recursion(num % 10)\n",
    "            else:\n",
    "                s += singles[num // 100] + \" Hundred \" + recursion(num % 100)\n",
    "            return s\n",
    "\n",
    "        s = \"\"\n",
    "        unit = int(1e9)\n",
    "        for i in range(3, -1, -1):\n",
    "            curNum = num // unit\n",
    "            if curNum:\n",
    "                num -= curNum * unit\n",
    "                s += recursion(curNum) + thousands[i] + \" \"\n",
    "            unit //= 1000\n",
    "        return s.strip()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numberToWords(self, num: int) -> str:\n",
    "        Int_dict = {0: '',1:' One', 2:' Two', 3:' Three', 4:' Four', 5:' Five', 6:' Six', 7:' Seven', 8:' Eight', 9:' Nine', 10:' Ten',\n",
    "         11:' Eleven', 12:' Twelve', 13:' Thirteen', 14:' Fourteen', 15:' Fifteen', 16:' Sixteen', 17:' Seventeen',\n",
    "        18:' Eighteen',19:' Nineteen', 20:' Twenty', 30:' Thirty', 40:' Forty', 50:' Fifty', 60:' Sixty', 70:' Seventy',\n",
    "         80:' Eighty', 90:' Ninety'}\n",
    "        H_dict = {1e9:' Billion', 1e6:' Million', 1e3:' Thousand', 100:' Hundred', 1:''}\n",
    "\n",
    "        if num == 0:\n",
    "            return 'Zero'\n",
    "\n",
    "        y = ''\n",
    "        for i,j in H_dict.items():\n",
    "            if num>=i:\n",
    "                s = num//i # 得到百位数\n",
    "                num = num - s*i\n",
    "                if s >= 100:\n",
    "                    a = s//100\n",
    "                    y = y + Int_dict[a] + ' Hundred'\n",
    "                    s = s - a*100\n",
    "                if s>=20:\n",
    "                    y = y + Int_dict[(s//10)*10] + Int_dict[s%10]\n",
    "                elif s<20:\n",
    "                    y = y+Int_dict[s]\n",
    "                y = y + j\n",
    "        return y[1:]\n",
    "\n",
    "\n",
    "\n"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
